Certifying 3-edge-connectivity
From MaRDI portal
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
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
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