Improved algorithms for graph four-connectivity
From MaRDI portal
Publication:808289
DOI10.1016/0022-0000(91)90004-OzbMATH Open0731.68086MaRDI QIDQ808289FDOQ808289
Authors: Arkady Kanevsky, Vijaya Ramachandran 
Publication date: 1991
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Recommendations
- Efficient algorithms for graphs with few \(P_4\)'s
- An improved exact algorithm for TSP in degree-4 graphs
- Linking four vertices in graphs of large connectivity
- Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
- An improved exact algorithm for TSP in graphs of maximum degree 4
- scientific article; zbMATH DE number 7740902
- On Four-Connecting a Triconnected Graph
- A constructive characterization of 4-connected graphs
- A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs
- A bound on 4-restricted edge connectivity of graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Depth-First Search and Linear Graph Algorithms
- Title not available (Why is that?)
- Network Flow and Testing Graph Connectivity
- Title not available (Why is that?)
- An Efficient Parallel Biconnectivity Algorithm
- Finding the Vertex Connectivity of Graphs
- Dividing a Graph into Triconnected Components
- An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
- A probabilistic algorithm for vertex connectivity of graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (16)
- An improved exact algorithm for TSP in graphs of maximum degree 4
- A linear-time certifying algorithm for recognizing generalized series-parallel graphs
- Yet another optimal algorithm for 3-edge-connectivity
- Maintaining the classes of 4-edge-connectivity in a graph on-line
- Graph ear decompositions and graph embeddings
- Safe separators for treewidth
- Title not available (Why is that?)
- Graph connectivity, partial words, and a theorem of Fine and Wilf
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Efficient algorithms for acyclic colorings of graphs
- Parallel search algorithms for graphs and trees
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Successive approximation in parallel graph algorithms
- A new graph triconnectivity algorithm and its parallelization
- Planarity testing in parallel
- Finding a small vertex cut on distributed networks
This page was built for publication: Improved algorithms for graph four-connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808289)
