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
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, 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, 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
