An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph

No abstract is available for this paper.

• Publication year

  2003

• Venue

  SIAM journal on computing (Print)

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/S0097539701392287
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A primal-dual schema based approximation algorithm for the element connectivity problem

  2002cited by this paper
• Approximation algorithms for minimum-cost k-vertex connected subgraphs

  2002cited by this paper
• On Rooted Node-Connectivity Problems

  2001cited by this paper
• Approximating node connectivity problems via set covers

  2000cited by this paper
• Using expander graphs to find vertex connectivity

  2000cited by this paper
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph

  1999cited by this paper
• Improved approximation algorithms for uniform connectivity problems

  1995cited by this paper
• Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

  1995cited by this paper
• Improved approximation algorithms for network design problems

  1994cited by this paper
• A representation for crossing set families with applications to submodular flow problems

  1993influential reference
• An application of submodular flows

  1989cited by this paper
• Surveys in Combinatorics: Connectivity and edge-connectivity in finite graphs

  1979cited by this paper

• A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph

  2023cites this paper
• An Improved Approximation Algorithm for the Minimum 2-Vertex-Connected Spanning Subgraph Problem

  2023cites this paper
• Survivable Network Design Revisited: Group-Connectivity

  2022cites this paper
• On the survivable network design problem with mixed connectivity requirements

  2019cites this paper
• D S ] 2 2 Ja n 20 19 A ( 4 + ǫ )-approximation for k-connected subgraphs

  2019cites this paper
• A $(4+\epsilon)$-approximation for $k$-connected subgraphs

  2019cites this paper
• Improved Algorithm for Minimum Power 2-Connected Subgraph Problem in Wireless Sensor Networks

  2018cites this paper
• Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

  2017cites this paper
• Improved Approximation Algorithms for Minimum Cost Node-Connectivity Augmentation Problems

  2017cites this paper
• Robust and Survivable Network Design Considering Uncertain Node and Link Failures

  2016cites this paper
• Surviving in Directed Graphs: A Polylogarithmic Approximation for Two-Connected Directed Steiner Tree

  2016cites this paper
• Approximation Algorithms for Connected Graph Factors of Minimum Weight

  2016cites this paper
• Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems

  2016cites this paper
• An Overview of Swarm Robotics for Search and Rescue Applications

  2016cites this paper
• Approximation Algorithms for k-Connected Graph Factors

  2015cites this paper
• Approximation and Online Algorithms

  2015cites this paper
• Economically Optimal Road Subnetwork

  2014cites this paper
• Darwinian swarm exploration under communication constraints: Initial deployment and fault-tolerance assessment

  2014cites this paper
• Approximating minimum-cost edge-covers of crossing biset-families

  2014cites this paper
• Low Level Clouds Analysis Relating to Synoptic Weather Types at Bratislava Airport

  2014cites this paper
• Evolutionary Robot Swarms Under Real-World Constraints

  2014cites this paper
• Models and Complexity of Problems of Design and Reconstruction of Telecommunication and Transport Systems

  2014cites this paper
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation

  2013cites this paper
• Approximability of Connected Factors

  2013cites this paper
• Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design

  2012cites this paper
• An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design

  2012cites this paper
• Approximation Techniques for Stochastic Combinatorial Optimization Problems

  2012cites this paper
• Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs

  2012influential citation
• Approximating minimum-cost edge-covers of crossing biset-families

  2012cites this paper
• An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity - (Extended Abstract)

  2011cites this paper
• An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem

  2011cites this paper
• Approximation Algorithms for Network Design and Orienteering

  2010cites this paper
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems

  2010cites this paper
• Deploying Sensor Networks With Guaranteed Fault Tolerance

  2010influential citation
• Tree embeddings for two-edge-connected network design

  2010cites this paper
• Approximating survivable networks with minimum number of steiner points

  2010cites this paper
• Approximation Algorithms for (S,T)-Connectivity Problems

  2010cites this paper
• An almost O(log k)-approximation for k-connected subgraphs

  2009influential citation
• Approximating Node-Connectivity Augmentation Problems

  2009cites this paper
• Approximating minimum-power edge-covers and 2, 3-connectivity

  2009cites this paper
• Online and stochastic survivable network design

  2009cites this paper
• Fault-tolerant deployment with k-connectivity and partial k-connectivity in sensor networks

  2009cites this paper
• A Graph Reduction Step Preserving Element-Connectivity and Applications

  2009cites this paper
• Network design for vertex connectivity

  2008cites this paper
• Approximating Minimum-Power k-Connectivity

  2008cites this paper
• Algorithms for Single-Source Vertex Connectivity

  2008cites this paper
• On k-connectivity problems with sharpened triangle inequality

  2008cites this paper
• Approximating Minimum-Power Degree and Connectivity Problems

  2008influential citation
• An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem

  2008influential citation
• On minimum power connectivity problems

  2007cites this paper
• Approximating Minimum-Cost Connectivity Problems

  2007cites this paper
• Approximating Minimum-Power Network Design Problems

  2007cites this paper
• An O ( log 2 k )-approximation algorithm for the k-vertex connected subgraph problem

  2007cites this paper
• Localized Movement Control for Fault Tolerance of Mobile Robot Networks

  2007cites this paper
• Handbook of Approximation Algorithms and Metaheuristics

  2007cites this paper
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems

  2006cites this paper
• Tight approximation algorithm for connectivity augmentation problems

  2006cites this paper
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems

  2006influential citation
• Network Design Via Iterative Rounding Of Setpair Relaxations

  2006influential citation
• Power optimization for connectivity problems

  2005influential citation
• Algorithms and complexity analyses for some combinatorial optimization problems

  2005cites this paper
• Approximating Rooted Connectivity Augmentation Problems

  2005cites this paper
• Approximation algorithms for network design with metric costs

  2005cites this paper
• Deploying sensor networks with guaranteed capacity and fault tolerance

  2005cites this paper
• Research on the Fault Tolerance Deployment in Sensor Networks

  2005cites this paper
• Approximate Minimum 2-Connected Subgraphs in Weighted Planar Graphs

  2004cites this paper
• A Memetic Algorithm for Minimum-Cost Vertex-Biconnectivity Augmentation of Graphs

  2003cites this paper
• Approximating Node Connectivity Problems via Set Covers

  2003cites this paper
• An iterative rounding 2-approximation algorithm for the element connectivity problem

  2001cites this paper
• Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

  1995cites this paper
• Network Design via Iterative Rounding of Setpair Relaxations

  year unknowncites this paper
• Mathematisches Forschungsinstitut Oberwolfach Graph Theory

  year unknowninfluential citation
• Deploying Sensor Nets with Guaranteed Capacity and Fault Tolerance

  year unknowncites this paper