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

DOI10.1137/110848311zbMATH Open1271.68242OpenAlexW2026181303MaRDI QIDQ2840980FDOQ2840980

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

Recommendations

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

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)

Cited In (8)

• Title not available (Why is that?)
• An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs
• Mondshein sequences (a.k.a. (2,1)-orders)
• Certifying 3-connectivity in linear time
• Computing vertex-disjoint paths in large graphs using MAOs
• 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: 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)