Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (2), 528-560
- https://doi.org/10.1137/s009753979833920x
Abstract
No abstract availableKeywords
This publication has 21 references indexed in Scilit:
- Approximating Biconnectivity in ParallelAlgorithmica, 1998
- A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph ProblemJournal of Algorithms, 1998
- Computing Minimal Spanning Subgraphs in Linear TimeSIAM Journal on Computing, 1995
- A Matroid Approach to Finding Edge Connectivity and Packing ArborescencesJournal of Computer and System Sciences, 1995
- The Number of Vertices of Degree k in a Minimally k-Edge-Connected GraphJournal of Combinatorial Theory, Series B, 1993
- On sparse subgraphs preserving connectivity propertiesJournal of Graph Theory, 1993
- Approximating matchings in parallelInformation Processing Letters, 1993
- Submodular functions in graph theoryDiscrete Mathematics, 1993
- Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex ConnectivitySIAM Journal on Computing, 1993
- Faster scaling algorithms for general graph matching problemsJournal of the ACM, 1991