A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph

No abstract is available for this paper.

• Publication year

  1999

• Venue

  J. Algorithms

• Publication date

  1999-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1006/jagm.1999.1006
• 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 3-Approximation Algorithm for Finding Optimum 4, 5-Vertex-Connected Spanning Subgraphs

  1999cited by this paper
• Improved Approximation Algorithms for Finding Optimum K-vertex Connected Spanning Subgraphs

  1998cited by this paper
• Finding Optimum k-vertex Connected Spanning Subgraphs: Improved Approximation Algorithms for k=3, 4, 5

  1997cited by this paper
• A better approximation ratio for the minimum k-edge-connected spanning subgraph problem

  1997cited by this paper
• Better Algorithms for Minimum Weight Vertex-Connectivity Problems

  1997cited by this paper
• Faster approximation algorithms for weighted triconnectivity augmentation problems

  1997influential reference
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems

  1997cited by this paper
• An approximation algorithm for minimum-cost vertex-connectivity problems

  1997influential reference
• Approximating minimum-size k-connected spanning subgraphs via matching

  1996influential reference
• Approximation algorithms for finding highly connected subgraphs

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

  1995influential reference
• A representation for crossing set families with applications to submodular flow problems

  1993cited by this paper
• Design of Survivable Networks

  1993cited by this paper
• Approximation Algorithms for Graph Augmentation

  1992cited by this paper
• An application of submodular flows

  1989cited by this paper
• Mathematical Programming The State of the Art, XIth International Symposium on Mathematical Programming, Bonn, Germany, August 23-27, 1982

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Extremal Graph Theory

  1978cited by this paper
• A theorem on n-connected graphs

  1969influential reference

• Streaming Algorithms for Network Design

  2025influential citation
• Node Connectivity Augmentation of Highly Connected Graphs

  2023cites this paper
• A logarithmic approximation algorithm for the activation edge multicover problem

  2023cites this paper
• Ghost Value Augmentation for k-Edge-Connectivity

  2023cites this paper
• Parameterized algorithms for node connectivity augmentation problems

  2022cites this paper
• Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle

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

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

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

  2019cites this paper
• The k-Connected Subgraph Problem

  2018cites this paper
• Designing WAN Topologies Under Redundancy Constraints 14

  2018cites this paper
• Improved approximation algorithms for k-connected m-dominating set problems

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

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

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

  2016influential citation
• Improved approximation algorithms for single-tiered relay placement

  2014cites this paper
• Degree Constrained Node-Connectivity Problems

  2013cites this paper
• An Eight-Approximation Algorithm for Computing Rooted Three-Vertex Connected Minimum Steiner Networks

  2013cites this paper
• Relay placement for two-connectivity

  2012cites this paper
• The Vital Core Connectivity Problem

  2012cites this paper
• Approximate Algorithms for Survivable Network Design

  2012cites this paper
• Efficient 2-Approximation Algorithms for Computing 2-Connected Steiner Minimal Networks

  2012influential citation
• Degree-Constrained Node-Connectivity

  2012cites this paper
• An algorithm for (n-3)-connectivity augmentation problem: Jump system approach

  2012cites this paper
• Approximation Algorithms for Network Connectivity Problems

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

  2012cites this paper
• Relay placement for fault tolerance in wireless networks in higher dimensions

  2011cites this paper
• Exact algorithms for network design problems using graph orientations

  2011cites this paper
• Approximating survivable networks with β-metric costs

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

  2011cites this paper
• Approximation and Online Algorithms

  2011cites this paper
• Approximating subset k-connectivity problems

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

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

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

  2008influential citation
• On extremal k-outconnected graphs

  2008cites this paper
• Network design for vertex connectivity

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

  2008cites this paper
• An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem

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

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

  2008cites this paper
• Approximating Minimum-Cost Connectivity Problems

  2007cites this paper
• On minimum power connectivity problems

  2007cites this paper
• Cactus tree type models for families of bisections of a set

  2007cites this paper
• Relay Placement and Movement Control for Realization of Fault-Tolerant Ad Hoc Networks

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

  2007cites this paper
• Robust design of wireless networks

  2006cites this paper
• Relay Placement Approximation Algorithms for k-Connectivity in Wireless Sensor Networks

  2006cites this paper
• Connectivitities and Power Assignment in Wireless Ad Hoc Networks

  2005cites this paper
• Power Assignment for k-Connectivity in Wireless Ad Hoc Networks

  2005influential citation
• Approximation algorithm for k-node connected subgraphs via critical graphs

  2004cites this paper
• On The Vertex-Connectivity Problem For Graphs With Sharpened Triangle Inequality

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

  2003cites this paper
• An Approximation Algorithm for the Minimum Weight Vertex-Connectivity Problem in Complete Graphs with Sharpened Triangle Inequality

  2003cites this paper
• Structural Cohesion and Embeddedness: A Hierarchical Concept of Social Groups

  2003cites this paper
• Structural Cohesion and Embeddedness : A Hierarchical Concept of Social Groups

  2003cites this paper
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph

  2003cites this paper
• Structural Cohesion and Embeddedness Structural Cohesion and Embeddedness : A hierarchical concept of social groups

  2003cites this paper
• Hardness of Approximation for Vertex-Connectivity Network Design Problems

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

  2002cites this paper
• Structural Cohesion and Embeddedness : A hierarchical conception of social groups

  2001cites this paper
• Social Cohesion and Embeddedness : A Hierarchical Conception of Social Groups

  2000cites this paper
• Approximating node connectivity problems via set covers

  2000cites this paper
• Structural Cohesion and Embeddedness : A hierarchical conception of social groups

  2000cites this paper
• Approximating multiroot 3‐outconnected subgraphs

  2000cites this paper
• A 3-Approximation Algorithm for Finding Optimum 4, 5-Vertex-Connected Spanning Subgraphs

  1999cites this paper
• Improving Resiliency of Overlay Networks for Streaming Applications

  year unknowncites this paper