Linear time algorithms for graph search and connectivity determination on complement graphs.

DOI10.1016/S0020-0190(98)00071-4zbMath1078.68675WikidataQ56474992 ScholiaQ56474992MaRDI QIDQ2583566

Hiro Ito, Mitsuo Yokoyama

Publication date: 17 January 2006

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Algorithms; Computational complexity; Connectivity; Graph search; Complement graph; Graph representation

Mathematics Subject Classification ID

68P10: Searching and sorting

68R10: Graph theory (including graph drawing) in computer science

68P05: Data structures

Related Items

Recognizing graphs without asteroidal triples, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, On the parallel computation of the biconnected and strongly connected co-components of graphs, On the Strongly Connected and Biconnected Components of the Complement of Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A linear time algorithm for computing 3-edge-connected components in a multigraph
• A matroid approach to finding edge connectivity and packing arborescences
• Efficient Algorithms for Geometric Graph Search Problems
• An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
• On sparse subgraphs preserving connectivity properties
• Dividing a Graph into Triconnected Components