Improved algorithms for graph four-connectivity

DOI10.1016/0022-0000(91)90004-OzbMath0731.68086MaRDI QIDQ808289

Vijaya Ramachandran, Arkady Kanevsky

Publication date: 1991

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

ARBITRARY CRCW PRAMseparating tripletstriconnected graphvertex four-connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Safe separators for treewidth, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Planarity testing in parallel, Graph ear decompositions and graph embeddings, Graph connectivity, partial words, and a theorem of Fine and Wilf, Efficient algorithms for acyclic colorings of graphs, A new graph triconnectivity algorithm and its parallelization, Parallel search algorithms for graphs and trees, Yet another optimal algorithm for 3-edge-connectivity, A linear-time certifying algorithm for recognizing generalized series-parallel graphs, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic algorithm for vertex connectivity of graphs
• An Efficient Parallel Biconnectivity Algorithm
• Finding the Vertex Connectivity of Graphs
• An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
• Network Flow and Testing Graph Connectivity
• Dividing a Graph into Triconnected Components
• Depth-First Search and Linear Graph Algorithms