Search results for "edge connectivity"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Ping Li, Guizhen Liu	The Edge Connectivity of Circuit Graphs of Matroids.	International Conference on Computational Science	2007	DBLP DOI BibTeX RDF	circuit graph of matroid, Matroid, edge connectivity
3	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
3	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
3	Richard Cole, Ramesh Hariharan	A fast algorithm for computing steiner edge connectivity.	STOC	2003	DBLP DOI BibTeX RDF	cactus trees, edge-connectivity, Steiner points
3	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
3	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
2	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
2	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
2	Abusayeed M. Saifullah, Yung H. Tsin	A Self-stabilizing Algorithm For 3-Edge-Connectivity.	ISPA	2007	DBLP DOI BibTeX RDF
2	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
2	Gruia Calinescu, Peng-Jun Wan	Range Assignment for Biconnectivity and k-Edge Connectivity in Wireless Ad Hoc Networks.	MONET	2006	DBLP DOI BibTeX RDF	approximation algorithms, distributed algorithm, NP-hardness, topology control, power assignment
2	Toshimasa Watanabe, Satoshi Taoka, Toshiya Mashima	Maximum weight matching-based algorithms for k-edge-connectivity augmentation of a graph.	ISCAS	2005	DBLP DOI BibTeX RDF
2	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
2	Zdenek Dvorak, Jan Kára, Daniel Král, Ondrej Pangrác	An Algorithm for Cyclic Edge Connectivity of Cubic Graphs.	SWAT	2004	DBLP DOI BibTeX RDF
2	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
2	L. Sunil Chandran	Edge Connectivity vs Vertex Connectivity in Chordal Graphs.	COCOON	2001	DBLP DOI BibTeX RDF
2	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
2	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
2	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
2	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
2	Weifa Liang, Brendan D. McKay	An NC Approximation Algorithm for Optimal k -Edge Connectivity Augmentation.	ISPAN	1999	DBLP DOI BibTeX RDF
2	Hiroshi Nagamochi, Peter Eades	Edge-Splitting and Edge-Connectivity Augmentation in Planar Graphs.	IPCO	1998	DBLP DOI BibTeX RDF
2	Hiroshi Nagamochi, Toru Hasunuma	An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate.	ISAAC	1998	DBLP DOI BibTeX RDF
2	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
2	John Hershberger, Monika Rauch, Subhash Suri	Fully Dynamic 2-Edge-Connectivity in Planar Graphs.	SWAT	1992	DBLP DOI BibTeX RDF
2	Toshimasa Watanabe, Toshiya Mashima, Satoshi Taoka	The k-Edge-Connectivity Augmentation Problem of Weighted Graphs.	ISAAC	1992	DBLP DOI BibTeX RDF
2	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
2	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
2	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
2	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
1	Tadachika Oki, Satoshi Taoka, Toshiya Mashima, Toshimasa Watanabe	A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints.	IEICE Transactions	2012	DBLP BibTeX RDF
1	Dongye Wang, Mei Lu	Edge fault tolerance of super edge connectivity for three families of interconnection networks.	Inf. Sci.	2012	DBLP DOI BibTeX RDF
1	Yingzhi Tian, Jixiang Meng, Xiaodong Liang	On Super Restricted Edge Connectivity of Half Vertex Transitive Graphs.	Graphs and Combinatorics	2012	DBLP DOI BibTeX RDF
1	Litao Guo, Ruifang Liu, Xiaofeng Guo	Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph.	Graphs and Combinatorics	2012	DBLP DOI BibTeX RDF
1	Huiqiu Lin, Jixiang Meng, Weihua Yang	Super restricted edge connectivity of regular graphs with two orbits.	Applied Mathematics and Computation	2012	DBLP DOI BibTeX RDF
1	Andreas Holtkamp, Dirk Meierling, Luis Pedro Montejano	k-restricted edge-connectivity in triangle-free graphs.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Yanmei Hong, Jixiang Meng, Zhao Zhang	Edge fault tolerance of graphs with respect to super edge connectivity.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Xue-Gang Chen, Shinya Fujita, Michitaka Furuya, Moo Young Sohn	Constructing connected bicritical graphs with edge-connectivity 2.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Jin-Xin Zhou	Super restricted edge connectivity of regular edge-transitive graphs.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Yingzhi Tian, Litao Guo, Jixiang Meng, Chengfu Qin	Inverse degree and super edge-connectivity.	Int. J. Comput. Math.	2012	DBLP DOI BibTeX RDF
1	Guy Even, Guy Kortsarz, Zeev Nutov	A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.	Inf. Process. Lett.	2011	DBLP DOI BibTeX RDF
1	Xiang-Lan Cao, Spela Brglez, Simon Spacapan, Elkin Vumar	On edge connectivity of direct products of graphs.	Inf. Process. Lett.	2011	DBLP DOI BibTeX RDF
1	Weihua Yang, Zhao Zhang, Xiaofeng Guo, Eddie Cheng, László Lipták	On the edge-connectivity of graphs with two orbits of the same size.	Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Jianping Ou	On optimizing edge connectivity of product graphs.	Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Marwan Al-Jubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine, Csaba D. Tóth, Pavel Valtr	Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three.	Algorithmica	2011	DBLP DOI BibTeX RDF
1	Alexander Araluze, Klavdija Kutnar, Luis Martínez, Dragan Marusic	Edge connectivity in difference graphs and some new constructions of partial sum families.	Eur. J. Comb.	2011	DBLP DOI BibTeX RDF
1	Suil O, Douglas B. West	Matching and edge-connectivity in regular graphs.	Eur. J. Comb.	2011	DBLP DOI BibTeX RDF
1	Abusayeed M. Saifullah, Yung H. Tsin	A self-stabilising algorithm for 3-edge-connectivity.	IJHPCN	2011	DBLP DOI BibTeX RDF
1	Jun Yuan, Aixia Liu	The k-Restricted Edge Connectivity of Balanced Bipartite Graphs.	Graphs and Combinatorics	2011	DBLP DOI BibTeX RDF
1	J. Ignacio Alvarez-Hamelin, Mariano G. Beiró, Jorge Rodolfo Busch	Understanding Edge Connectivity in the Internet through Core Decomposition.	Internet Mathematics	2011	DBLP DOI BibTeX RDF
1	Robert E. L. Aldred, Yoshimi Egawa, Jun Fujisawa, Katsuhiro Ota, Akira Saito	The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity.	Journal of Graph Theory	2011	DBLP DOI BibTeX RDF
1	Nhat X. Lam, Trac N. Nguyen, Min Kyung An, Dung T. Huynh	Dual power assignment optimization for k-edge connectivity in WSNs.	SECON	2011	DBLP DOI BibTeX RDF
1	Qinghai Liu, Xiaohui Huang, Zhao Zhang	Restricted Edge Connectivity of Harary Graphs.	COCOA	2011	DBLP DOI BibTeX RDF
1	Nachshon Cohen, Zeev Nutov	A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
1	Zeev Nutov	Approximating minimum power covers of intersecting families and directed edge-connectivity problems.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Yingzhi Tian, Jixiang Meng	On super restricted edge-connectivity of edge-transitive graphs.	Discrete Mathematics	2010	DBLP DOI BibTeX RDF
1	Jørgen Bang-Jensen, Marco Chiarandini, Peter Morling	A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation.	Networks	2010	DBLP DOI BibTeX RDF
1	Toshimasa Ishii, Yoko Akiyama, Hiroshi Nagamochi	Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs.	Algorithmica	2010	DBLP DOI BibTeX RDF
1	David Pritchard	k-Edge-Connectivity: Approximation and LP Relaxation	CoRR	2010	DBLP BibTeX RDF
1	Wai Shing Fung, Nicholas J. A. Harvey	Graph Sparsification by Edge-Connectivity and Random Spanning Trees	CoRR	2010	DBLP BibTeX RDF
1	Suil O, Sebastian M. Cioaba	Edge-Connectivity, Eigenvalues, and Matchings in Regular Graphs.	SIAM J. Discrete Math.	2010	DBLP DOI BibTeX RDF
1	Jianping Ou	On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks.	Applied Mathematics and Computation	2010	DBLP DOI BibTeX RDF
1	Zoltán Király, Ben Cosh, Bill Jackson	Local edge-connectivity augmentation in hypergraphs is NP-complete.	Discrete Applied Mathematics	2010	DBLP DOI BibTeX RDF
1	Jianping Ou	On maximal 3-restricted edge connectivity of regular graphs.	Int. J. Comput. Math.	2010	DBLP DOI BibTeX RDF
1	Tadachika Oki, Satoshi Taoka, Toshimasa Watanabe	A Parallel Algorithm for 2-Edge-Connectivity Augmentation of a Connected Graph with Multipartition Constraints.	ICNC	2010	DBLP DOI BibTeX RDF
1	David Pritchard	k-Edge-Connectivity: Approximation and LP Relaxation.	WAOA	2010	DBLP DOI BibTeX RDF
1	Roland Grappe, Attila Bernáth, Zoltán Szigeti	Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph.	Electronic Notes in Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Toshimasa Ishii	Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs.	Discrete Optimization	2009	DBLP DOI BibTeX RDF
1	Peter Dankelmann, Angelika Hellwig, Lutz Volkmann	Inverse degree and edge-connectivity.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Paul A. Catlin, Hong-Jian Lai, Yehong Shao	Edge-connectivity and edge-disjoint spanning trees.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Jinyang Chen, Jixiang Meng, Lihong Huang	Super edge-connectivity of mixed Cayley graph.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Jianping Ou, Xiaohong Cheng, Jichang Wu	On 3-restricted edge connectivity of undirected binary Kautz graphs.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Shiying Wang, Shangwei Lin	The k-restricted edge connectivity of undirected Kautz graphs.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Bing Wang, Zhao Zhang	On cyclic edge-connectivity of transitive graphs.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Shiying Wang, Shangwei Lin, Chunfang Li	Sufficient conditions for super k-restricted edge connectivity in graphs of diameter 2.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Frank Boesch, Daniel Gross, John T. Saccoman, L. William Kazmierczak, Charles L. Suffel, Antonius Suhartomo	A generalization of an edge-connectivity theorem of Chartrand.	Networks	2009	DBLP DOI BibTeX RDF
1	Shangwei Lin, Shiying Wang	Super p-restricted edge connectivity of line graphs.	Inf. Sci.	2009	DBLP DOI BibTeX RDF
1	Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov	A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF	Approximation algorithms, graphs, connectivity
1	José Ignacio Alvarez-Hamelin, Mariano G. Beiró, Jorge Rodolfo Busch	Understanding edge-connectivity in the Internet through core-decomposition	CoRR	2009	DBLP BibTeX RDF
1	Min Lü, Guo-Liang Chen, Xi-Rong Xu	On super edge-connectivity of product graphs.	Applied Mathematics and Computation	2009	DBLP DOI BibTeX RDF
1	Takuro Fukunaga, Hiroshi Nagamochi	Eulerian detachments with local edge-connectivity.	Discrete Applied Mathematics	2009	DBLP DOI BibTeX RDF
1	You Lu, Jun-Ming Xu, Xinmin Hou	Bounded edge-connectivity and edge-persistence of Cartesian product of graphs.	Discrete Applied Mathematics	2009	DBLP DOI BibTeX RDF
1	Camino Balbuena, Diego González-Moreno, Xavier Marcote	On the 3-restricted edge connectivity of permutation graphs.	Discrete Applied Mathematics	2009	DBLP DOI BibTeX RDF
1	Yung H. Tsin	Yet another optimal algorithm for 3-edge-connectivity.	J. Discrete Algorithms	2009	DBLP DOI BibTeX RDF
1	Michael Brinkmeier	Increasing the Edge Connectivity by One in O(lambda_G n^2 log* n) Expected Time.	CTW	2009	DBLP BibTeX RDF
1	Marwan Al-Jubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine, Csaba D. Tóth	Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs.	ISAAC	2009	DBLP DOI BibTeX RDF
1	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
1	Anand Bhalgat, Ramesh Hariharan	Fast edge orientation for unweighted graphs.	SODA	2009	DBLP DOI BibTeX RDF
1	Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi	Online and stochastic survivable network design.	STOC	2009	DBLP DOI BibTeX RDF	approximation algorithms, online algorithms, network design problems
1	Sharon Marko, Dana Ron	Approximating the distance to properties in bounded-degree and general sparse graphs.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF	Sublinear approximation algorithms, property testing, graph properties, distance approximation
1	Satyajeet Ahuja, Srinivasan Ramasubramanian, Marwan Krunz	Single-link failure detection in all-optical networks using monitoring cycles and paths.	IEEE/ACM Trans. Netw.	2009	DBLP DOI BibTeX RDF	fault localization, all-optical networks
1	Sameera Poduri, Sundeep Pattem, Bhaskar Krishnamachari, Gaurav S. Sukhatme	Using Local Geometry for Tunable Topology Control in Sensor Networks.	IEEE Trans. Mob. Comput.	2009	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Nitish Korula	A Graph Reduction Step Preserving Element-Connectivity and Applications.	ICALP	2009	DBLP DOI BibTeX RDF
1	Takuro Fukunaga	Graph Orientations with Set Connectivity Requirements.	ISAAC	2009	DBLP DOI BibTeX RDF
1	Zhao Zhang	Extra edge connectivity and isoperimetric edge connectivity.	Discrete Mathematics	2008	DBLP DOI BibTeX RDF
1	Dingjun Lou, Wei Wang	Characterization of graphs with infinite cyclic edge connectivity.	Discrete Mathematics	2008	DBLP DOI BibTeX RDF
1	Zoltán Szigeti	Edge-connectivity augmentation of graphs over symmetric parity families.	Discrete Mathematics	2008	DBLP DOI BibTeX RDF
1	Fengxia Liu, Jixiang Meng	Edge-connectivity of regular graphs with two orbits.	Discrete Mathematics	2008	DBLP DOI BibTeX RDF
1	Peter Dankelmann, Simon Mukwembi, Henda C. Swart	Average Distance and Edge-Connectivity II.	SIAM J. Discrete Math.	2008	DBLP DOI BibTeX RDF
1	Peter Dankelmann, Simon Mukwembi, Henda C. Swart	Average Distance and Edge-Connectivity I.	SIAM J. Discrete Math.	2008	DBLP DOI BibTeX RDF