Linear time algorithms for graph search and connectivity determination on complement graphs.
From MaRDI portal
Publication:2583566
DOI10.1016/S0020-0190(98)00071-4zbMath1078.68675WikidataQ56474992 ScholiaQ56474992MaRDI QIDQ2583566
Publication date: 17 January 2006
Published in: Information Processing Letters (Search for Journal in Brave)
Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Related Items (8)
Simple DFS on the complement of a graph and on partially complemented digraphs ⋮ On the parallel computation of the biconnected and strongly connected co-components of graphs ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Recognizing graphs without asteroidal triples ⋮ On the chromatic index of join graphs and triangle-free graphs with large maximum degree ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ On the Strongly Connected and Biconnected Components of the Complement of Graphs ⋮ A fast branching algorithm for cluster vertex deletion
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Linear time algorithms for graph search and connectivity determination on complement graphs.
