Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching

DOI10.1137/S009753979833920XzbMath1049.90104MaRDI QIDQ4507363

Ramakrishna Thurimella, Joseph Cheriyan

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

NP-complete problemsgraphsmatchingsdirected graphsnetwork designgraph connectivityapproximation algorithmsedge connectivitydegree constrained subgraphsnode connectivity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (27)

On computing the 2-vertex-connected components of directed graphs ⋮ Minimum 2-vertex strongly biconnected spanning directed subgraph problem ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ Pruning 2-connected graphs ⋮ Box-total dual integrality and edge-connectivity ⋮ Hereditary systems and greedy-type algorithms. ⋮ On approximating the \(d\)-girth of a graph ⋮ Small \(\ell\)-edge-covers in \(k\)-connected graphs ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ Approximating the smallest k -edge connected spanning subgraph by LP-rounding ⋮ Network flow spanners ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Bulk-robust combinatorial optimization ⋮ Parameterizing above or below guaranteed values ⋮ On Approximating the d-Girth of a Graph ⋮ Fast exact algorithms for survivable network design with uniform requirements ⋮ Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs ⋮ On the maximum size of a minimal \(k\)-edge connected augmentation ⋮ Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs ⋮ Computing the 2-blocks of directed graphs ⋮ An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree ⋮ Flexible graph connectivity

This page was built for publication: Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching