Search results for "k-edge-connected"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
51	Jean Fonlupt, Ali Ridha Mahjoub	Critical Extreme Points of the 2-Edge Connected Spanning Subgraph Polytope.	IPCO	1999	DBLP DOI BibTeX RDF	2-edge connected graph, critical extreme point, Polytope, cut
48	Anand Bhalgat, Ramesh Hariharan	Fast edge orientation for unweighted graphs.	SODA	2009	DBLP DOI BibTeX RDF
47	Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki	Augmenting a (k-1)-Vertex-Connected Multigraph l-Edge-Connected and k-Vertex-Connected Multigraph.	Algorithmica	2006	DBLP DOI BibTeX RDF	Undirected multigraph, Graph augmentation, Deterministic algorithm, Edge-connectivity, Vertex-connectivity, Polynomial time approximation algorithm
47	Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki	Augmenting a (kappa-1)-Vertex-Connected Multigraph to an iota-Edge-Connected and kappa-Vertex-Connected Multigraph.	ESA	1999	DBLP DOI BibTeX RDF
46	Alexandr V. Kostochka, Vladimir A. Tashkinov	Decomposing Graphs into Long Paths.	Order	2003	DBLP DOI BibTeX RDF	edge-decompositions of graphs, 2-edge-connected graphs
44	Haruko Okamura	Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs.	Graphs Comb.	2005	DBLP DOI BibTeX RDF	k-edge-connected, disjoint 2 paths, 2-reducible
42	Enrico Nardelli, Guido Proietti, Peter Widmayer	Swapping a Failing Edge of a Single Source Shortest Paths Tree Is Good and Fast.	Algorithmica	2003	DBLP DOI BibTeX RDF
40	Robert Carr, R. Ravi 0001	A New Bound for the 2-Edge Connected Subgraph Problem.	IPCO	1998	DBLP DOI BibTeX RDF
40	Harold N. Gabow	A Framework for Cost-scaling Algorithms for Submodular Flow Problems	FOCS	1993	DBLP DOI BibTeX RDF	cost-scaling algorithms, submodular flow problems, dijoin, edge-connectivity orientation, k-edge-connected orientation, minimum-cost k-edge-connected orientation, integer linear programming, vertices, vertex weights, minimum-cost network flow
38	Koichi Wada 0001, Akinari Takaki, Kimio Kawaguchi	Efficient Algorithms for a Mixed k-Partition Problem of Graphs without Specifying Bases.	WG	1994	DBLP DOI BibTeX RDF
38	Alex R. Berg, Tibor Jordán	Minimally k-Edge-Connected Directed Graphs of Maximal Size.	Graphs Comb.	2005	DBLP DOI BibTeX RDF	Minimally k-edge-connected, Directed graphs, Edge-connectivity
37	András Frank, Zoltán Király	Parity Constrained k-Edge-Connected Orientations.	IPCO	1999	DBLP DOI BibTeX RDF
35	Tibor Jordán	Edge-Splitting Problems with Demands.	IPCO	1999	DBLP DOI BibTeX RDF
35	Pierre Fraigniaud, Nicolas Nisse	Connected Treewidth and Connected Graph Searching.	LATIN	2006	DBLP DOI BibTeX RDF
32	Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi	Fast edge splitting and Edmonds' arborescence construction for unweighted graphs.	SODA	2008	DBLP BibTeX RDF
32	Hiroshi Nagamochi, Peter Eades	Edge-Splitting and Edge-Connectivity Augmentation in Planar Graphs.	IPCO	1998	DBLP DOI BibTeX RDF
32	Ou Jianping, Fuji Zhang	Super Restricted Edge Connectivity of Regular Graphs.	Graphs Comb.	2005	DBLP DOI BibTeX RDF	AMS Classification 05C40
32	Weifa Liang, Brendan D. McKay	An NC Approximation Algorithm for Optimal k -Edge Connectivity Augmentation.	ISPAN	1999	DBLP DOI BibTeX RDF
32	Weifa Liang, George Havas	NC Approximation Algorithms for 2-Connectivity Augmentation in a Graph.	Euro-Par	1997	DBLP DOI BibTeX RDF
31	MohammadAli Safari, Mohammad R. Salavatipour	A Constant Factor Approximation for Minimum lambda-Edge-Connected k-Subgraph with Metric Costs.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
31	Toshimasa Ishii, Hiroshi Nagamochi	Simultaneous Augmentation of Two Graphs to an l-Edge-Connected Graph and a Biconnected Graph.	ISAAC	2000	DBLP DOI BibTeX RDF
31	Harold N. Gabow	An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph.	SODA	2002	DBLP BibTeX RDF
31	Corinne Lucet, Jean-Francois Manouvrier, Jacques Carlier	Evaluating Network Reliability and 2-Edge-Connected Reliability in Linear Time for Bounded Pathwidth Graphs.	Algorithmica	2000	DBLP DOI BibTeX RDF
30	Xiaofeng Gu	Packing spanning trees and spanning 2-connected k-edge-connected essentially (2k-1)-edge-connected subgraphs.	J. Comb. Optim.	2017	DBLP DOI BibTeX RDF
29	Guido Proietti	Dynamic Maintenance Versus Swapping: An Experimental Study on Shortest Paths Trees.	WAE	2000	DBLP DOI BibTeX RDF
29	Anna Galluccio, Guido Proietti	A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation.	ISAAC	2002	DBLP DOI BibTeX RDF	Edge-Connectivity Augmentation, Approximation Algorithms, Network Survivability
29	Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko	Approximating Minimum-Power Degree and Connectivity Problems.	LATIN	2008	DBLP DOI BibTeX RDF
29	Iztok Banic, Janez Zerovnik	Edge Fault-Diameter of Cartesian Product of Graphs.	SIROCCO	2007	DBLP DOI BibTeX RDF	Cartesian graph products, edge fault-diameter, interconnection network
28	Shuang Zhao, Zongqing Chen 0001, Weihua Yang, Jixiang Meng	Edge fault-tolerance analysis of maximally edge-connected graphs and super edge-connected graphs.	J. Comput. Syst. Sci.	2021	DBLP DOI BibTeX RDF
28	Marwan Al-Jubeh, Michael Hoffmann 0001, Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth	Convex Partitions with 2-Edge Connected Dual Graphs.	COCOON	2009	DBLP DOI BibTeX RDF
28	Artur Czumaj, Michelangelo Grigni, Papa A. Sissokho, Hairong Zhao	Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs.	SODA	2004	DBLP BibTeX RDF
26	Ambreen Shahnaz, Thomas Erlebach	Approximating fault-tolerant Steiner subgraphs in heterogeneous wireless networks.	IWCMC	2010	DBLP DOI BibTeX RDF	2-edge-connected Steiner subgraph, quasi unit disk graph, unit disk graph
26	Aleksej Di Salvo, Guido Proietti	Swapping a Failing Edge of a Shortest Paths Tree by Minimizing the Average Stretch Factor.	SIROCCO	2004	DBLP DOI BibTeX RDF
26	Anupam Gupta 0001, Ravishankar Krishnaswamy, R. Ravi 0001	Online and stochastic survivable network design.	STOC	2009	DBLP DOI BibTeX RDF	approximation algorithms, online algorithms, network design problems
26	Satoshi Taoka, Toshimasa Watanabe	The (sigma+1)-Edge-Connectivity Augmentation Problem without Creating Multiple Edges of a Graph.	IFIP TCS	2000	DBLP DOI BibTeX RDF
26	André Berger, Artur Czumaj, Michelangelo Grigni, Hairong Zhao	Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs.	ESA	2005	DBLP DOI BibTeX RDF
26	András Frank, Zoltán Király	Graph Orientations with Edge-connection and Parity Constraints.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) Classes: 05C75, 05C40
26	Yefim Dinitz, Ronit Nossenson	Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph.	SWAT	2000	DBLP DOI BibTeX RDF
26	Dora Giammarresi, Giuseppe F. Italiano	Dynamic 2- and 3-Connectivity on Planar Graphs (Preliminary Version).	SWAT	1992	DBLP DOI BibTeX RDF
26	Andreas Schwill	Shorest Edge-Disjoint Paths in Graphs.	STACS	1989	DBLP DOI BibTeX RDF
26	David Pritchard	Fast Distributed Computation of Cuts Via Random Circulations.	ICALP (1)	2008	DBLP DOI BibTeX RDF
26	Koichi Wada 0001, Wei Chen 0003	Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases.	WG	1998	DBLP DOI BibTeX RDF
26	Samir Khuller, Uzi Vishkin	Biconnectivity Approximations and Graph Carvings.	J. ACM	1994	DBLP DOI BibTeX RDF	sparse subgraphs, connectivity, biconnectivity
25	Weiyi Zhang 0001, Guoliang Xue, Jian Tang 0008, Krishnaiyan Thulasiraman	Linear time construction of redundant trees for recovery schemes enhancing QoP and QoS.	INFOCOM	2005	DBLP DOI BibTeX RDF
25	Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki	Optimal Augmentation of a 2-Vertex-Connected Multigraph to a k-Edge-Connected and 3-Vertex-Connected Multigraph.	J. Comb. Optim.	2000	DBLP DOI BibTeX RDF
24	Efstratios Rappos, Eleni Hadjiconstantinou	An Ant Colony Heuristic for the Design of Two-Edge Connected Flow Networks.	ANTS Workshop	2004	DBLP DOI BibTeX RDF
24	Harold N. Gabow, Suzanne Gallagher	Iterated rounding algorithms for the smallest k-edge connected spanning subgraph.	SODA	2008	DBLP BibTeX RDF
24	Jean Fonlupt, Ali Ridha Mahjoub	Critical extreme points of the 2-edge connected spanning subgraph polytope.	Math. Program.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90B10, 90C27, 90C57
24	Hiroshi Nagamochi, Toshihide Ibaraki	An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree.	COCOON	1999	DBLP DOI BibTeX RDF
23	Xuemei Liu, Jixiang Meng, Yingzhi Tian	On forcibly k-edge-connected and forcibly super edge-connected uniform hypergraphic sequences.	J. Supercomput.	2023	DBLP DOI BibTeX RDF
23	Rocío M. Casablanca, Lucas Mol, Ortrud R. Oellermann	Average connectivity of minimally 2-connected graphs and average edge-connectivity of minimally 2-edge-connected graphs.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
23	Shuang Zhao, Yingzhi Tian, Jixiang Meng	Degree Sequence Conditions for Maximally Edge-Connected and Super Edge-Connected Hypergraphs.	Graphs Comb.	2020	DBLP DOI BibTeX RDF
23	Lutz Volkmann	Sufficient conditions for maximally edge-connected and super-edge-connected graphs depending on the clique number.	Discuss. Math. Graph Theory	2019	DBLP DOI BibTeX RDF
23	Sebastian Milz, Lutz Volkmann	Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number.	Discret. Math.	2018	DBLP DOI BibTeX RDF
23	Shiying Wang, Nana Zhao	Degree conditions for graphs to be maximally k-restricted edge connected and super k-restricted edge connected.	Discret. Appl. Math.	2015	DBLP DOI BibTeX RDF
23	Lutz Volkmann	Degree sequence conditions for maximally edge-connected and super-edge-connected oriented graphs depending on the clique number.	Ars Comb.	2011	DBLP BibTeX RDF
23	Lutz Volkmann	Sufficient conditions for maximally edge-connected and super-edge-connected oriented graphs depending on the clique number.	Ars Comb.	2010	DBLP BibTeX RDF
23	Angelika Hellwig, Lutz Volkmann	Sufficient conditions for graphs to be lambda'-optimal, super-edge-connected, and maximally edge-connected.	J. Graph Theory	2005	DBLP DOI BibTeX RDF
23	Tibor Jordán	On minimally k-edge-connected graphs and shortest k-edge-connected Steiner networks.	Discret. Appl. Math.	2003	DBLP DOI BibTeX RDF
22	Joseph Cheriyan, Adrian Vetta	Approximation algorithms for network design with metric costs.	STOC	2005	DBLP DOI BibTeX RDF	metric costs, approximation algorithms, graph connectivity
22	Davide Bilò, Guido Proietti	Augmenting the Edge-Connectivity of a Spider Tree.	ISAAC	2004	DBLP DOI BibTeX RDF	Edge-Connectivity Augmentation, Spider Tress, Graph Algorithms, NP-hardness, Network Survivability
22	Abusayeed M. Saifullah, Yung H. Tsin	A Self-stabilizing Algorithm For 3-Edge-Connectivity.	ISPA	2007	DBLP DOI BibTeX RDF
22	Hiroshi Nagamochi, Toshihide Ibaraki	A Faster Edge Splitting Algorithm in Multigraphs and its Application to the Edge-Connectivity Augmentation Problem.	IPCO	1995	DBLP DOI BibTeX RDF
22	Yefim Dinitz	The 3-Edge-Components and a Structural Description of All 3-Edge-Cuts in a Graph.	WG	1992	DBLP DOI BibTeX RDF
22	Joe Anderson, Haidong Wu	An Extremal Problem on Contractible Edges in 3-Connected Graphs.	Graphs Comb.	2006	DBLP DOI BibTeX RDF
21	Sven Oliver Krumke, Peter Merz, Tim Nonner, Katharina Rupp	Distributed Approximation Algorithms for Finding 2-Edge-Connected Subgraphs.	OPODIS	2007	DBLP DOI BibTeX RDF
21	Bernard Fortz, Ali Ridha Mahjoub, S. Thomas McCormick, Pierre Pesneau	Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut.	Math. Program.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (1991) 90B10, 90C27, 90C57
21	Li Yang	k-Edge Connected Neighborhood Graph for Geodesic Distance Estimation and Nonlinear Data Projection.	ICPR (1)	2004	DBLP DOI BibTeX RDF
20	Hongsik Choi, Suresh Subramaniam 0001, Hyeong-Ah Choi	Loopback recovery from double-link failures in optical mesh networks.	IEEE/ACM Trans. Netw.	2004	DBLP DOI BibTeX RDF	3-edge-connected graph, double-link failure, loopback recovery, wavelength division multiplexing (WDM), shared risk link group, link protection
20	András A. Benczúr	A Representation of Cuts within 6/5 Times the Edge Connectivity with Applications.	FOCS	1995	DBLP DOI BibTeX RDF	edge connected graph, planar geometric representation, edge cuts, query structure, edge splitting, edge augmentation problem, computational complexity, data structures, computational geometry, cuts, edge connectivity
19	Beat Gfeller	Faster Swap Edge Computation in Minimum Diameter Spanning Trees.	ESA	2008	DBLP DOI BibTeX RDF
19	Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung	Degree Bounded Network Design with Metric Costs.	FOCS	2008	DBLP DOI BibTeX RDF
19	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov	Power optimization for connectivity problems.	Math. Program.	2007	DBLP DOI BibTeX RDF
19	Gruia Calinescu, Peng-Jun Wan	Range Assignment for Biconnectivity and k-Edge Connectivity in Wireless Ad Hoc Networks.	Mob. Networks Appl.	2006	DBLP DOI BibTeX RDF	approximation algorithms, distributed algorithm, NP-hardness, topology control, power assignment
19	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov	Power Optimization for Connectivity Problems.	IPCO	2005	DBLP DOI BibTeX RDF
19	Gruia Calinescu, Peng-Jun Wan	Range Assignment for High Connectivity in Wireless Ad Hoc Networks.	ADHOC-NOW	2003	DBLP DOI BibTeX RDF
19	Artur Czumaj, Andrzej Lingas	Fast Approximation Schemes for Euclidean Multi-connectivity Problems.	ICALP	2000	DBLP DOI BibTeX RDF
19	Artur Czumaj, Andrzej Lingas	A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity.	ICALP	1998	DBLP DOI BibTeX RDF
19	R. Ravi 0001, Balaji Raghavachari, Philip N. Klein	Approximation Through Local Optimality: Designing Networks with Small Degree.	FSTTCS	1992	DBLP DOI BibTeX RDF
18	Morteza Hasanvand	The Existence of Planar 4-Connected Essentially 6-Edge-Connected Graphs with No Claw-Decompositions.	Graphs Comb.	2023	DBLP DOI BibTeX RDF
18	Haiyang Liu, Qinghai Liu, Yanmei Hong	Connectivity keeping trees in 3-connected or 3-edge-connected graphs.	Discret. Math.	2023	DBLP DOI BibTeX RDF
18	Toru Hasunuma	Connectivity preserving trees in k-connected or k-edge-connected graphs.	J. Graph Theory	2023	DBLP DOI BibTeX RDF
18	Jan Ekstein, Baoyindureng Wu, Liming Xiong	Connected Even Factors in the Square of Essentially 2-Edge-connected Graph.	Electron. J. Comb.	2017	DBLP DOI BibTeX RDF
18	Baigong Zheng	Linear-time approximation schemes for planar minimum three-edge connected and three-vertex connected spanning subgraphs.	CoRR	2017	DBLP BibTeX RDF
18	Hengzhe Li, Yuxing Yang, Baoyindureng Wu	2-Edge connected dominating sets and 2-Connected dominating sets of a graph.	J. Comb. Optim.	2016	DBLP DOI BibTeX RDF
18	G. Sethuraman 0001, A. Velankanni, S. Anbarasu, V. Vijayalakshmi 0002	Cycle Partition of Two-Connected and Two-Edge Connected Graphs.	Math. Comput. Sci.	2015	DBLP DOI BibTeX RDF
18	Amr Elmasry, Yung H. Tsin	On Finding Sparse Three-Edge-Connected and Three-Vertex-Connected Spanning subgraphs.	Int. J. Found. Comput. Sci.	2014	DBLP DOI BibTeX RDF
18	Takuro Fukunaga	All 4-Edge-Connected HHD-Free Graphs are \mathbbZ3-Connected.	Graphs Comb.	2011	DBLP DOI BibTeX RDF
18	Shiying Wang, Guozhen Zhang, Xiuli Wang	Sufficient conditions for maximally edge-connected graphs and arc-connected digraphs.	Australas. J Comb.	2011	DBLP BibTeX RDF
18	Mark Bilinski, Bill Jackson, Jie Ma 0002, Xingxing Yu	Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs.	J. Comb. Theory, Ser. B	2011	DBLP DOI BibTeX RDF
18	Jin-Xin Zhou, Yan-Quan Feng	Super-connected but not super edge-connected graphs.	Inf. Process. Lett.	2010	DBLP DOI BibTeX RDF
18	Ângela Mestre	Generating connected and 2-edge connected graphs.	J. Graph Algorithms Appl.	2009	DBLP DOI BibTeX RDF
18	Hong-Jian Lai, Lianying Miao, Yehong Shao	Every line graph of a 4-edge-connected graph is I-connected.	Eur. J. Comb.	2009	DBLP DOI BibTeX RDF
18	Angelika Hellwig, Lutz Volkmann	Maximally edge-connected and vertex-connected graphs and digraphs: A survey.	Discret. Math.	2008	DBLP DOI BibTeX RDF
18	Dongju Kim, Daekeun Lim	2-connected and 2-edge-connected Steinhaus graphs.	Discret. Math.	2002	DBLP DOI BibTeX RDF
18	Koichi Wada 0001, Kimio Kawaguchi, Yupin Luo	Fault-tolerant network routings for (k + 1)-node connected and (k + 1)-edge connected graphs.	Syst. Comput. Jpn.	1987	DBLP DOI BibTeX RDF
18	Yung H. Tsin	A Simple 3-Edge-Connected Component Algorithm.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
18	André Berger, Michelangelo Grigni	Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs.	ICALP	2007	DBLP DOI BibTeX RDF
18	Dieter Vandenbussche, George L. Nemhauser	The 2-Edge-Connected Subgraph Polyhedron.	J. Comb. Optim.	2005	DBLP DOI BibTeX RDF	traveling salesman problem, network design, polyhedra, edge-connectivity
18	Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson	Approximating the smallest k-edge connected spanning subgraph by LP-rounding.	SODA	2005	DBLP BibTeX RDF