Approximating Node Connectivity Problems via Set Covers

No abstract is available for this paper.

• Publication year

  2003

• Venue

  Algorithmica

• Publication date

  2003-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00453-003-1027-4
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

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

  2004cited by this paper
• Approximation Algorithms for NP-Hard Problems

  2004cited by this paper
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph

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

  2001influential reference
• A 3-Approximation Algorithm for Finding Optimum 4, 5-Vertex-Connected Spanning Subgraphs

  1999influential reference
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph

  1999cited by this paper
• A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

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

  1997cited by this paper
• Approximation algorithms for finding highly connected subgraphs

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

  1995influential reference
• On the Optimal Vertex-Connectivity Augmentation

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

  1995cited by this paper
• A faster strongly polynomial minimum cost flow algorithm

  1993cited 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
• Matrix multiplication via arithmetic progressions

  1987cited by this paper
• A Polynomial Algorithm for b-Matchings: An Alternative Approach

  1987cited by this paper
• Minimal n-fach zusammenhängende Digraphen

  1985cited by this paper
• On the Relationship between the Biconnectivity Augmentation and Traveling Salesman Problems

  1982cited by this paper
• Ecken vom Gradn in minimalenn-fach zusammenhängenden Graphen

  1972cited by this paper
• Network Design via Iterative Rounding of Setpair Relaxations

  year unknowncited by this paper

• Bicriteria approximation for k-edge-connectivity

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

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

  2022cites this paper
• On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs

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

  2019cites this paper
• Approximating k-Connected m-Dominating Sets

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

  2019influential citation
• Designing WAN Topologies Under Redundancy Constraints 14

  2018cites this paper
• The k-Connected Subgraph Problem

  2018cites this paper
• Approximating bounded-degree spanning trees and connected factors with leaves

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

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

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

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

  2016cites this paper
• Optimized bi-connected federation of multiple sensor network segments

  2016cites this paper
• Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance

  2015cites this paper
• Topology management techniques for tolerating node failures in wireless sensor networks: A survey

  2014cites this paper
• Approximation Algorithms for Connected Graph Factor Problems

  2014cites this paper
• Topology Management Techniques for Tolerating Node Failure

  2014cites this paper
• Approximability status of Survivable Network problems

  2014cites this paper
• Power optimization in ad hoc wireless network topology control with biconnectivity requirements

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

  2013cites this paper
• Degree Constrained Node-Connectivity Problems

  2013cites this paper
• The Vital Core Connectivity Problem

  2012cites this paper
• Survivable network activation problems

  2012cites this paper
• Degree-Constrained Node-Connectivity

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

  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
• 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 Algorithms for Network Connectivity Problems

  2012cites this paper
• Approximating subset k-connectivity problems

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

  2011influential citation
• Exact algorithms for network design problems using graph orientations

  2011cites this paper
• Approximation and Online Algorithms

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

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

  2010cites this paper
• Algorithms for k-fault tolerant power assignments in wireless sensor networks

  2010cites this paper
• Approximation algorithms for minimum-cost k-( S , T ) connected digraphs

  2010cites this paper
• Tree embeddings for two-edge-connected network design

  2010cites this paper
• Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks

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

  2010cites this paper
• Approximating Node-Connectivity Augmentation Problems

  2009cites this paper
• Online and stochastic survivable network design

  2009cites 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
• Edge Splitting-off and Network Design Problems

  2009cites this paper
• Approximating survivable networks with 𝛽 -quasi-metric costs

  2009cites this paper
• Approximating survivable networks with-metric costs

  2009influential citation
• Approximating Minimum-Power Degree and Connectivity Problems

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

  2008cites this paper
• Degree Bounded Network Design with Metric Costs

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

  2008cites this paper
• Network design for vertex connectivity

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

  2008cites this paper
• Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks

  2007cites this paper
• On minimum power connectivity problems

  2007cites this paper
• A simple randomized scheme for constructing low-weight k-connected spanning subgraphs with applications to distributed algorithms

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

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

  2007cites this paper
• Approximating Minimum-Cost Connectivity Problems

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

  2007cites this paper
• Handbook of Approximation Algorithms and Metaheuristics

  2007cites this paper
• Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks

  2007cites this paper
• Robust design of wireless networks

  2006influential citation
• Relay Placement Approximation Algorithms for k-Connectivity in Wireless Sensor Networks

  2006cites this paper
• Hardness and approximation algorithms of some graph problems

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

  2006cites this paper
• Relay Placement for Higher Order Connectivity in Wireless Sensor Networks

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

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

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

  2005influential citation
• Range Augmentation Problems in Static Ad-Hoc Wireless Networks

  2005cites this paper
• Approximating Rooted Connectivity Augmentation Problems

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

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

  2005influential citation
• Power optimization for connectivity problems

  2005cites this paper
• Approximation algorithm for k-node connected subgraphs via critical graphs

  2004cites this paper
• Wireless Sensor Networks and Computational Geometry

  2004cites this paper
• IterativeRounding 2-Approximation Algorithms for Minimum-CostVertex Connectivity Problems

  2003cites this paper
• Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks

  2003influential citation
• Hardness of Approximation for Vertex-Connectivity Network Design Problems

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

  2001cites this paper
• Research Plan

  year unknowncites this paper
• Network Design via Iterative Rounding of Setpair Relaxations

  year unknowncites this paper