Contractions, Removals, and Certifying 3-Connectivity in Linear Time

DOI10.1137/110848311zbMath1271.68242OpenAlexW2026181303MaRDI QIDQ2840980

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

3-connected graphcertifying algorithmconstruction sequenceinductive characterizationnested subdivisions

Mathematics Subject Classification ID

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

Related Items (5)

A simple certifying algorithm for 3-edge-connectivity ⋮ Certifying 3-edge-connectivity ⋮ Unnamed Item ⋮ Computing vertex-disjoint paths in large graphs using MAOs ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders)

This page was built for publication: Contractions, Removals, and Certifying 3-Connectivity in Linear Time