Certifying 3-edge-connectivity

DOI10.1007/s00453-015-0075-xzbMath1356.05150arXiv1211.6553OpenAlexW2164746840MaRDI QIDQ513265

Adrian Neumann, Kurt Mehlhorn, Jens M. Schmidt

Publication date: 3 March 2017

Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.6553

zbMATH Keywords

edge connectivitycertifying algorithmconstruction sequence

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (9)

On objects dual to tree-cut decompositions ⋮ Quantum graphs which optimize the spectral gap ⋮ Combinatorial acyclicity models for potential‐based flows ⋮ Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs ⋮ Unnamed Item ⋮ A simple certifying algorithm for 3-edge-connectivity ⋮ Edge-orders ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders) ⋮ A linear-time certifying algorithm for recognizing generalized series-parallel graphs

Uses Software

• LEDA
• AutoCorres

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Path-based depth-first search for strong and biconnected components
• Certifying algorithms
• A simple 3-edge-connected component algorithm
• Yet another optimal algorithm for 3-edge-connectivity
• Rubber bands, convex embeddings and graph connectivity
• A linear time algorithm for computing 3-edge-connected components in a multigraph
• Nearly optimal binary search trees
• A simple test on 2-vertex- and 2-edge-connectivity
• A framework for the verification of certifying computations
• Contractions, Removals, and Certifying 3-Connectivity in Linear Time
• PERFECT STOCHASTIC SUMMATION IN HIGH ORDER FEYNMAN GRAPH EXPANSIONS
• The Cluster Editing Problem: Implementations and Experiments
• Algorithmic Aspects of Graph Connectivity
• Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs
• Finding triconnected components of graphs
• Efficient Planarity Testing
• A Reduction Method for Edge-Connectivity in Graphs
• Dividing a Graph into Triconnected Components
• Minimum cuts in near-linear time

This page was built for publication: Certifying 3-edge-connectivity