Contractions, removals, and certifying 3-connectivity in linear time

DOI10.1137/110848311MaRDI QIDQ2840980zbMATHOpenAlexFDO

Authors Jens M. Schmidt

Publication date 24 July 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/e96433e88c18127644d80f00b41ebe3f51800d69

zbMATH Keywords

certifying algorithm3-connected graphconstruction sequenceinductive characterizationnested subdivisions

Mathematics Subject Classification ID

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

Recommendations

• Certifying 3-connectivity in linear time
• Construction sequences and certifying 3-connectivity
• Construction sequences and certifying 3-connectedness

Cited in

(8)

• Construction sequences and certifying 3-connectivity
• A simple certifying algorithm for 3-edge-connectivity
• scientific article; zbMATH DE number 7561367 (Why is no real title available?)
• Certifying 3-connectivity in linear time
• Mondshein sequences (a.k.a. (2,1)-orders)
• An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs
• Construction sequences and certifying 3-connectedness
• Computing vertex-disjoint paths in large graphs using MAOs

This page was built for publication: Contractions, removals, and 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 Q2840980)