Search results for "edge-connectivity"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
71	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
58	Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, Anand Bhalgat	An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs.	STOC	2007	DBLP DOI BibTeX RDF	Gomory-Hu tree, cut tree, steiner edge connectivity, edge connectivity, min cut
57	Mikkel Thorup	Fully-dynamic min-cut.	STOC	2001	DBLP DOI BibTeX RDF
56	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
52	Weifa Liang, Richard P. Brent, Hong Shen	Fully Dynamic Maintenance of k-Connectivity in Parallel.	IEEE Trans. Parallel Distributed Syst.	2001	DBLP DOI BibTeX RDF	2-edge/vertex connectivity, 3-edge/vertex connectivity, parallel algorithm design and analysis, dynamic data structures, graph problems, NC algorithms
50	Richard Cole 0001, Ramesh Hariharan	A fast algorithm for computing steiner edge connectivity.	STOC	2003	DBLP DOI BibTeX RDF	cactus trees, edge-connectivity, Steiner points
48	Hiroshi Nagamochi, Peter Eades	Edge-Splitting and Edge-Connectivity Augmentation in Planar Graphs.	IPCO	1998	DBLP DOI BibTeX RDF
46	David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig	Sparsification - a technique for speeding up dynamic graph algorithms.	J. ACM	1997	DBLP DOI BibTeX RDF	edge and vertex connectivity, minimum spanning trees, dynamic graph algorithms
43	Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup	Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.	J. ACM	2001	DBLP DOI BibTeX RDF	2-edge connectivity, connectivity, minimum spanning tree, dynamic graph algorithms, Biconnectivity
43	Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi	Efficient algorithms for computing all low s-t edge connectivities and related problems.	SODA	2007	DBLP BibTeX RDF
42	Anna Galluccio, Guido Proietti	Polynomial Time Algorithms for Edge-Connectivity Augmentation of Hamiltonian Paths.	ISAAC	2001	DBLP DOI BibTeX RDF	2-edge connectivity, Graph, Hamiltonian path, network survivability, augmentation
42	Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi	Fast edge splitting and Edmonds' arborescence construction for unweighted graphs.	SODA	2008	DBLP BibTeX RDF
41	Hiro Ito, Yuichiro Itatsu, Hideyuki Uehara, Mitsuo Yokoyama, Motoyasu Ito	Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets.	ISAAC	2000	DBLP DOI BibTeX RDF
41	Chandra Chekuri, Nitish Korula	A Graph Reduction Step Preserving Element-Connectivity and Applications.	ICALP (1)	2009	DBLP DOI BibTeX RDF
41	Hiroshi Nagamochi, S. Nakamura, Toshihide Ibaraki	A Simplified Õ(nm) Time Edge-Splitting Algorithm in Undirected Graphs.	Algorithmica	2000	DBLP DOI BibTeX RDF	Edge splitting, Deterministic algorithm, Undirected graph, Polynomial algorithm, Minimum cut, Edge-connectivity, Multigraph
41	Anand Bhalgat, Ramesh Hariharan	Fast edge orientation for unweighted graphs.	SODA	2009	DBLP DOI BibTeX RDF
40	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
39	Ping Li 0064, Guizhen Liu	The Edge Connectivity of Circuit Graphs of Matroids.	International Conference on Computational Science (3)	2007	DBLP DOI BibTeX RDF	circuit graph of matroid, Matroid, edge connectivity
38	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
36	Mikkel Thorup	Fully-Dynamic Min-Cut.	Comb.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68Q25, 68W05, 94C12, 94C15, 90B25, 68R10, 05C85, 05C40, 90B10
36	Attila Bernáth, Tamás Király	A New Approach to Splitting-Off.	IPCO	2008	DBLP DOI BibTeX RDF
35	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
35	Weifa Liang, Brendan D. McKay	An NC Approximation Algorithm for Optimal k -Edge Connectivity Augmentation.	ISPAN	1999	DBLP DOI BibTeX RDF
35	András Frank, Tamás Király	Combined Connectivity Augmentation and Orientation Problems.	IPCO	2001	DBLP DOI BibTeX RDF
34	Jon M. Kleinberg, Mark Sandler 0002, Aleksandrs Slivkins	Network failure detection and graph connectivity.	SODA	2004	DBLP BibTeX RDF
34	Artur Czumaj, Andrzej Lingas	Fast Approximation Schemes for Euclidean Multi-connectivity Problems.	ICALP	2000	DBLP DOI BibTeX RDF
33	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
33	Joseph Cheriyan, Adrian Vetta	Approximation algorithms for network design with metric costs.	STOC	2005	DBLP DOI BibTeX RDF	metric costs, approximation algorithms, graph connectivity
33	Shimon Even, Gene Itkis, Sergio Rajsbaum	On Mixed Connectivity Certificates (Extended Abstract).	ESA	1995	DBLP DOI BibTeX RDF
32	Zeev Nutov	Approximating Steiner Networks with Node Weights.	LATIN	2008	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	Takuro Fukunaga, Hiroshi Nagamochi	Network Design with Edge-Connectivity and Degree Constraints.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Degree constraint, (m,n)-VRP, Approximation algorithm, TSP, Vehicle routing problem, Edge-connectivity
31	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
31	Greg N. Frederickson	Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees	FOCS	1991	DBLP DOI BibTeX RDF	ambivalent data structures, dynamic maintenance, dynamic 2-edge-connectivity, k smallest spanning trees, weighted undirected graph, embedded planar graph, query, edges, vertices
31	Harold N. Gabow	Applications of a Poset Representation to Edge Connectivity and Graph Rigidity	FOCS	1991	DBLP DOI BibTeX RDF	graphic matroids, poset representation, graph rigidity, rigid subgraphs, rigid bars, directed graphs, undirected graphs, minimum cuts, time bound, edge connectivity, labeling algorithm
31	András Frank	Augmenting Graphs to Meet Edge-Connectivity Requirements	FOCS	1990	DBLP DOI BibTeX RDF	node costs, minimum number, min-max formula, minimum-cost augmentation problem, edge costs, time complexity, polynomial-time algorithm, polynomial time, edge-connectivity
31	Dalit Naor, Dan Gusfield, Charles U. Martel	A Fast Algorithm for Optimally Increasing the Edge-Connectivity	FOCS	1990	DBLP DOI BibTeX RDF	undirected unweighted graph, input parameter, edge augmentation problem, optimal augmentation, time complexity, time bound, edge-connectivity
31	Tibor Jordán	Edge-Splitting Problems with Demands.	IPCO	1999	DBLP DOI BibTeX RDF
31	Artur Czumaj, Andrzej Lingas, Hairong Zhao	Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem.	ICALP	2002	DBLP DOI BibTeX RDF
31	L. Sunil Chandran	Edge Connectivity vs Vertex Connectivity in Chordal Graphs.	COCOON	2001	DBLP DOI BibTeX RDF
30	Zdenek Dvorák 0001, Jan Kára, Daniel Král, Ondrej Pangrác	An Algorithm for Cyclic Edge Connectivity of Cubic Graphs.	SWAT	2004	DBLP DOI BibTeX RDF
30	Samir Khuller, Uzi Vishkin	Biconnectivity Approximations and Graph Carvings.	J. ACM	1994	DBLP DOI BibTeX RDF	sparse subgraphs, connectivity, biconnectivity
29	Abusayeed M. Saifullah, Yung H. Tsin	A Self-stabilizing Algorithm For 3-Edge-Connectivity.	ISPA	2007	DBLP DOI BibTeX RDF
28	Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige	Minimum Cost Source Location Problems with Flow Requirements.	Algorithmica	2008	DBLP DOI BibTeX RDF	Approximation algorithm, Combinatorial optimization, Connectivity, Location problem
27	Apostolos N. Papadopoulos, Apostolos Lyritsis, Yannis Manolopoulos	SkyGraph: an algorithm for important subgraph discovery in relational graphs.	Data Min. Knowl. Discov.	2008	DBLP DOI BibTeX RDF	Skyline processing, Graph mining, Edge connectivity
27	Michael Brinkmeier, Jeremias Werner, Sven Recknagel	Communities in graphs and hypergraphs.	CIKM	2007	DBLP DOI BibTeX RDF	cohesive group, community, image segmentation, components, graph, hypergraph, edge-connectivity, document collection
26	Lisa Fleischer	A 2-Approximation for Minimum Cost {0, 1, 2} Vertex Connectivity.	IPCO	2001	DBLP DOI BibTeX RDF
26	Mikkel Thorup, David R. Karger	Dynamic Graph Algorithms with Applications.	SWAT	2000	DBLP DOI BibTeX RDF
26	Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovic, Ralf Klasing, Guido Proietti, Sebastian Seibert, Walter Unger	On k-Edge-Connectivity Problems with Sharpened Triangle Inequality.	CIAC	2003	DBLP DOI BibTeX RDF
25	Satoshi Taoka, Toshimasa Watanabe	Minimum Augmentation to k-Edge-Connect Specified Vertices of a Graph.	ISAAC	1994	DBLP DOI BibTeX RDF
24	Julia Chuzhoy, Sanjeev Khanna	Algorithms for Single-Source Vertex Connectivity.	FOCS	2008	DBLP DOI BibTeX RDF
24	Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige	Minimum Cost Source Location Problems with Flow Requirements.	LATIN	2006	DBLP DOI BibTeX RDF
24	Yonghao Lai, Xiaohui Hua	Component edge connectivity and extra edge connectivity of alternating group networks.	J. Supercomput.	2024	DBLP DOI BibTeX RDF
24	Xiaoxia Lin, Keke Wang, Meng Zhang 0005, Hong-Jian Lai	Bounding ℓ-edge-connectivity in edge-connectivity.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
24	Qifan Zhang, Liqiong Xu, Weihua Yang	Reliability analysis of the augmented cubes in terms of the extra edge-connectivity and the component edge-connectivity.	J. Parallel Distributed Comput.	2021	DBLP DOI BibTeX RDF
24	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
24	Litao Guo, Mingzu Zhang, Shaohui Zhai, Liqiong Xu	Relation of Extra Edge Connectivity and Component Edge Connectivity for Regular Networks.	Int. J. Found. Comput. Sci.	2021	DBLP DOI BibTeX RDF
24	Junye Ma, Qingguo Li, Xiangnan Zhou	Fuzzy edge connectivity and fuzzy local edge connectivity with applications to communication networks.	Fuzzy Sets Syst.	2021	DBLP DOI BibTeX RDF
24	Rong-Xia Hao, Mei-Mei Gu, Jou-Ming Chang	Relationship between extra edge connectivity and component edge connectivity for regular graphs.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
24	Pingshan Li, Min Xu 0005	Fault-tolerant strong Menger (edge) connectivity and 3-extra edge-connectivity of balanced hypercubes.	Theor. Comput. Sci.	2018	DBLP DOI BibTeX RDF
24	Litao Guo, Xiaofeng Guo	Local restricted edge connectivity and restricted edge connectivity of graphs.	Ars Comb.	2016	DBLP BibTeX RDF
24	Chunxiang Wang	On Edge-Connectivity and Super Edge-Connectivity of Interconnection Networks Modeled by Product Graphs.	Discret. Math. Algorithms Appl.	2010	DBLP DOI BibTeX RDF
24	Zhao Zhang	Extra edge connectivity and isoperimetric edge connectivity.	Discret. Math.	2008	DBLP DOI BibTeX RDF
24	Camino Balbuena, Martín Cera, Ana Diánez, Pedro García-Vázquez, Xavier Marcote	On the edge-connectivity and restricted edge-connectivity of a product of graphs.	Discret. Appl. Math.	2007	DBLP DOI BibTeX RDF
24	Zhao Zhang, Jinjiang Yuan	Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimal.	Discret. Math.	2007	DBLP DOI BibTeX RDF
24	Camino Balbuena, Daniela Ferrero	Edge-connectivity and super edge-connectivity of P2-path graphs.	Discret. Math.	2003	DBLP DOI BibTeX RDF
24	Hyun Soo Kang, Yong-Woo Kim, TaeYong Kim 0003	A Temporal Error Concealment Method Based on Edge Adaptive Boundary Matching.	PSIVT	2006	DBLP DOI BibTeX RDF
24	Farshad Faghih, Michael Smith 0002	Combining spatial and scale-space techniques for edge detection to provide a spatially adaptive wavelet-based noise filtering algorithm.	IEEE Trans. Image Process.	2002	DBLP DOI BibTeX RDF
23	Mohammad Taghi Hajiaghayi, Nicole Immorlica, Vahab S. Mirrokni	Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks.	IEEE/ACM Trans. Netw.	2007	DBLP DOI BibTeX RDF	Ad hoc networks, approximation algorithms, topology control, graph model, power conservation, graph properties
23	Prabhakar Gubbala, Balaji Raghavachari	Finding k-Connected Subgraphs with Minimum Average Weight.	LATIN	2004	DBLP DOI BibTeX RDF
23	Alex Fit-Florea, David W. Matula	Determining all pairs edge connectivity of a 4-regular graph in O(\|V\|).	AICCSA	2005	DBLP DOI BibTeX RDF
23	John Hershberger 0001, Monika Rauch, Subhash Suri	Fully Dynamic 2-Edge-Connectivity in Planar Graphs.	SWAT	1992	DBLP DOI BibTeX RDF
22	Samir Khuller, Ramakrishna Thurimella	Approximation Algorithms for Graph Augmentation.	ICALP	1992	DBLP DOI BibTeX RDF
21	Gruia Calinescu, Peng-Jun Wan	Range Assignment for High Connectivity in Wireless Ad Hoc Networks.	ADHOC-NOW	2003	DBLP DOI BibTeX RDF
20	Erkut Erdem, Aysun Sancar-Yilmaz, Sibel Tari	Mumford-Shah Regularizer with Spatial Coherence.	SSVM	2007	DBLP DOI BibTeX RDF
20	Yaniv Altshuler, Vladimir Yanovski, Daniel Vainsencher, Israel A. Wagner, Alfred M. Bruckstein	On Minimal Perimeter Polyminoes.	DGCI	2006	DBLP DOI BibTeX RDF
20	L. Sunil Chandran, N. S. Narayanaswamy	On the Arrangement of Cliques in Chordal Graphs with Respect to the Cuts.	COCOON	2004	DBLP DOI BibTeX RDF
20	Michal Katz, Nir A. Katz, Amos Korman, David Peleg	Labeling schemes for flow and connectivity.	SODA	2002	DBLP BibTeX RDF
20	Pei-Chi Huang, Hsin-Wen Wei, Wan-Chen Lu, Wei-Kuan Shih, Tsan-sheng Hsu	Smallest Bipartite Bridge-Connectivity Augmentation.	Algorithmica	2009	DBLP DOI BibTeX RDF	2-edge-connectivity, Bridge-connectivity, Bipartite graph augmentation, Data security
20	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
20	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
20	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
20	Hiroshi Nagamochi, Peter Eades	An Edge-Splitting Algorithm in Planar Graphs.	J. Comb. Optim.	2003	DBLP DOI BibTeX RDF	edge splitting, planar graph, undirected graph, minimum cut, edge-connectivity, multigraph, outerplanar graph
20	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
20	David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig	Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract)	FOCS	1992	DBLP DOI BibTeX RDF	minimum spanning forests, best swap, graph 2-edge-connectivity, data structures, graph connectivity, dynamic graph algorithms, sparsification
19	Toshimasa Watanabe, Satoshi Taoka, Toshiya Mashima	Maximum weight matching-based algorithms for k-edge-connectivity augmentation of a graph.	ISCAS (3)	2005	DBLP DOI BibTeX RDF
19	Hiroshi Nagamochi, Toru Hasunuma	An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate.	ISAAC	1998	DBLP DOI BibTeX RDF
19	Toshimasa Watanabe, Toshiya Mashima, Satoshi Taoka	The k-Edge-Connectivity Augmentation Problem of Weighted Graphs.	ISAAC	1992	DBLP DOI BibTeX RDF
19	Chandra Chekuri, Sanjeev Khanna	Algorithms for 2-Route Cut Problems.	ICALP (1)	2008	DBLP DOI BibTeX RDF
19	Faisal N. Abu-Khzam, Michael A. Langston	Graph Coloring and the Immersion Order.	COCOON	2003	DBLP DOI BibTeX RDF
19	Ran Gu, Xiaofeng Gu, Yongtang Shi, Hua Wang 0003	ℓ $\ell $ -Connectivity and ℓ $\ell $ -edge-connectivity of random graphs.	J. Graph Theory	2022	DBLP DOI BibTeX RDF
19	Keiko Kotani, Shuto Nishida	Existence of 3-factors in K1, n-free graphs with connectivity and edge-connectivity conditions.	Australas. J Comb.	2021	DBLP BibTeX RDF
19	Miaomiao Han, Jiaao Li, Xueliang Li 0001, Meiling Wang	Group connectivity under 3-edge-connectivity.	J. Graph Theory	2021	DBLP DOI BibTeX RDF
19	Cheng-Kuan Lin, Liang Ma, Jianxi Fan, Lih-Hsing Hsu, Yuan-Hsiang Teng	The Conditional-(g, d, k)-Connectivity and Conditional-(g, d, k)-edge-Connectivity on the Hypercubes.	Fundam. Informaticae	2020	DBLP DOI BibTeX RDF
19	Jun Liang 0002, Meixin Du, Ruihua Nie, Zhihao Liang, Zheng Li	Distributed Algorithms for Cyclic Edge Connectivity and Cyclic Vertex Connectivity of Cubic Graphs.	ICDSP	2020	DBLP DOI BibTeX RDF
19	Shipeng Wang, Shoichi Tsuchiya, Liming Xiong	Forbidden Pairs for Equality of Connectivity and Edge-Connectivity of Graphs.	Graphs Comb.	2019	DBLP DOI BibTeX RDF
19	Abusayeed Saifullah	2-Edge-Connectivity and 2-Vertex-Connectivity of an Asynchronous Distributed Network.	CoRR	2019	DBLP BibTeX RDF
19	Da-Wei Yang, Yan-Quan Feng, Jaeun Lee, Jin-Xin Zhou	On extra connectivity and extra edge-connectivity of balanced hypercubes.	Appl. Math. Comput.	2018	DBLP DOI BibTeX RDF
19	Huazhong Lü	On extra connectivity and extra edge-connectivity of balanced hypercubes.	Int. J. Comput. Math.	2017	DBLP DOI BibTeX RDF
19	Qing Cui, Qiuping Qian, Lingping Zhong	The maximum atom-bond connectivity index for graphs with edge-connectivity one.	Discret. Appl. Math.	2017	DBLP DOI BibTeX RDF