A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
From MaRDI portal
Publication:1186788
DOI10.1007/BF01758778zbMath0763.05065OpenAlexW1996575062MaRDI QIDQ1186788
Toshihide Ibaraki, Hiroshi Nagamochi
Publication date: 28 June 1992
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01758778
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (85)
On computing minimum\((s,t)\)-cuts in digraphs ⋮ Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time ⋮ \(k\)-connectivity and decomposition of graphs into forests ⋮ Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity ⋮ Recent developments in maximum flow algorithms ⋮ Optimal per-edge processing times in the semi-streaming model ⋮ Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs ⋮ Minimum degree orderings ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs ⋮ Sparse connectivity certificates via MA orderings in graphs ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ ON FINDING SPARSE THREE-EDGE-CONNECTED AND THREE-VERTEX-CONNECTED SPANNING SUBGRAPHS ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Maintaining minimum spanning trees in dynamic graphs ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Efficiently enumerating all spanning trees of a plane 3-tree (extended abstract) ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ An Improved Algorithm for Finding Cycles Through Elements ⋮ A plane graph representation of triconnected graphs ⋮ The disjoint paths problem in quadratic time ⋮ Graphs of separability at most 2 ⋮ On biconnected and fragile subgraphs of low diameter ⋮ Output-sensitive reporting of disjoint paths (extended abstract) ⋮ Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs ⋮ Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries ⋮ Construction sequences and certifying 3-connectivity ⋮ An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs ⋮ Efficient algorithms for a mixed k-partition problem of graphs without specifying bases ⋮ A note on the minimization of symmetric and general submodular functions ⋮ Faster cut sparsification of weighted graphs ⋮ Complexity of the min-max (regret) versions of min cut problems ⋮ Certifying algorithms ⋮ Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ On the decay of crossing numbers ⋮ Compact cactus representations of all non-trivial min-cuts ⋮ Approximating minimum cuts under insertions ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ On mixed connectivity certificates ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ A linear time algorithm for computing 3-edge-connected components in a multigraph ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ A cubic kernel for feedback vertex set and loop cutset ⋮ Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs ⋮ Unnamed Item ⋮ Independence free graphs and vertex connectivity augmentation ⋮ Improved Algorithms for the 2-Vertex Disjoint Paths Problem ⋮ Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\) ⋮ Sparse graph certificates for mixed connectivity ⋮ Finding a small vertex cut on distributed networks ⋮ Network flow spanners ⋮ Reconstructing edge-disjoint paths faster ⋮ Minimum Cuts of Simple Graphs in Almost Always Linear Time ⋮ Bisecting a 4-connected graph with three resource sets ⋮ Minimum cut in \(O(m \log^2 n)\) time ⋮ Cycle-connected mixed graphs and related problems ⋮ Cycle-connected mixed graphs and related problems ⋮ Implementing an efficient minimum capacity cut algorithm ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ On mixed connectivity certificates ⋮ A General Framework for Graph Sparsification ⋮ Minimizing symmetric submodular functions ⋮ Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs ⋮ A robust algorithm for bisecting a triconnected graph with two resource sets ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs ⋮ Fast Augmenting Paths by Random Sampling from Residual Graphs ⋮ I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs ⋮ Linear time algorithms for graph search and connectivity determination on complement graphs. ⋮ Approximating minimum size \{1,2\}-connected networks ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time ⋮ Minimum cost source location problem with vertex-connectivity requirements in digraphs ⋮ On the complexity of the vector connectivity problem ⋮ An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
Cites Work
This page was built for publication: A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
