Certifying 3-connectivity in linear time

DOI10.1007/978-3-642-31594-7_66zbMATH Open1272.05206OpenAlexW197905035MaRDI QIDQ2843301FDOQ2843301

Authors: Jens M. Schmidt 

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31594-7_66

Recommendations

• Contractions, removals, and certifying 3-connectivity in linear time
• Construction sequences and certifying 3-connectivity
• A simple certifying algorithm for 3-edge-connectivity

zbMATH Keywords

connected graphsconstruction method3 edge connectivity3 vertex connectivity3-connectivity test

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40)

Cited In (6)

• An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs
• Why depth-first search efficiently identifies two and three-connected graphs
• Contractions, removals, and certifying 3-connectivity in linear time
• A simple certifying algorithm for 3-edge-connectivity
• Construction sequences and certifying 3-connectedness
• Construction sequences and certifying 3-connectivity

This page was built for publication: Certifying 3-connectivity in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843301)