Approximation algorithms and hardness results for labeled connectivity problems

DOI10.1007/s10878-007-9044-xzbMath1149.90166OpenAlexW2085720608MaRDI QIDQ2426652

Jérôme Monnot, Danny Segev, Refael Hassin

Publication date: 23 April 2008

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9044-x

zbMATH Keywords

Approximation algorithmsHardness of approximationLabeled connectivity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (26)

Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ Complexity of column generation in network design with path-based survivability mechanisms ⋮ Labeled cuts in graphs ⋮ The label cut problem with respect to path length and label frequency ⋮ Sequence Hypergraphs ⋮ Complexity and approximation results on the shared transportation problem ⋮ Secluded connectivity problems ⋮ On the hardness of labeled correlation clustering problem: a parameterized complexity view ⋮ Sequence Hypergraphs: Paths, Flows, and Cuts ⋮ Approximation and hardness results for label cut and related problems ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Unnamed Item ⋮ On the maximum disjoint paths problem on edge-colored graphs ⋮ Improved approximation bounds for the minimum constraint removal problem ⋮ Labeled traveling salesman problems: complexity and approximation ⋮ The parameterized complexity of some minimum label problems ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ A note on the clustered set covering problem ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ The maximum labeled path problem ⋮ Algorithms and complexity results for labeled correlation clustering problem ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ The complexity of bottleneck labeled graph problems ⋮ Approximate tradeoffs on weighted labeled matroids ⋮ Minimum Cell Connection in Line Segment Arrangements ⋮ Finding disjoint paths in networks with star shared risk link groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• On the hardness of approximating minimum vertex cover
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• A modified greedy heuristic for the set covering problem with improved worst case bound
• On approximation algorithms for the minimum satisfiability problem
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• The budgeted maximum coverage problem
• Approximating MIN 2-SAT and MIN 3-SAT
• Local search for the minimum label spanning tree problem with bounded color classes.
• A note on the minimum label spanning tree.
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Improved low-degree testing and its applications
• Approximation Schemes for the Restricted Shortest Path Problem
• Spanning trees with many or few colors in edge-colored graphs
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Efficient probabilistically checkable proofs and applications to approximations
• A simple efficient approximation scheme for the restricted shortest path problem

This page was built for publication: Approximation algorithms and hardness results for labeled connectivity problems