Construction sequences and certifying 3-connectivity

DOI10.1007/S00453-010-9450-9MaRDI QIDQ2428654zbMATH OpenOpenAlexFDO

Authors Jens M. Schmidt

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-9450-9

zbMATH Keywords

algorithms and data structures3-connectedremovable edgescertifying algorithmconstruction sequenceTutte contraction

Mathematics Subject Classification ID

Data structures (68P05) Connectivity (05C40)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3166039 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3308985 (Why is no real title available?)
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Checking geometric programs or verification of geometric structures
• Construction sequences and certifying 3-connectedness
• Designing programs that check their work
• Dividing a Graph into Triconnected Components
• Finding triconnected components of graphs
• Kuratowski's theorem
• Reflections on graph theory
• Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• \(E_{11}\) and M theory

Cited in

(4)

• Contractions, removals, and certifying 3-connectivity in linear time
• Certifying 3-connectivity in linear time
• On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
• Construction sequences and certifying 3-connectedness

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: Construction sequences and certifying 3-connectivity

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