An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs
From MaRDI portal
Publication:2429326
DOI10.1007/s00453-010-9481-2zbMath1239.05107MaRDI QIDQ2429326
Jens M. Schmidt, Kurt Mehlhorn, Amr Elmasry
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9481-2
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
05C45: Eulerian and Hamiltonian graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for a special case of disjoint set union
- Contractible edges in 3-connected graphs
- Rubber bands, convex embeddings and graph connectivity
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A new graph triconnectivity algorithm and its parallelization
- A survey on contractible edges in graphs of a prescribed vertex connectivity
- Progress on Certifying Algorithms
- Dynamic orthogonal segment intersection search
- Finding the Vertex Connectivity of Graphs
- Nonseparating cycles inK-Connected graphs
- Efficient Planarity Testing
- An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk