Approximation algorithms and hardness results for labeled connectivity problems
From MaRDI portal
Publication:2426652
DOI10.1007/S10878-007-9044-XzbMATH Open1149.90166OpenAlexW2085720608MaRDI QIDQ2426652FDOQ2426652
Authors: Refael Hassin, Jérôme Monnot, Danny Segev 
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
Recommendations
- Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
- On the minimum label spanning tree problem
- The minimum labeling spanning trees
- Local search for the minimum label spanning tree problem with bounded color classes.
- Approximation and hardness results for label cut and related problems
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- Approximation algorithms for combinatorial problems
- Approximation Schemes for the Restricted Shortest Path Problem
- A simple efficient approximation scheme for the restricted shortest path problem
- On the ratio of optimal integral and fractional covers
- Title not available (Why is that?)
- Title not available (Why is that?)
- A General Approximation Technique for Constrained Forest Problems
- On approximating the longest path in a graph
- On the hardness of approximating minimum vertex cover
- On approximation algorithms for the minimum satisfiability problem
- On the minimum label spanning tree problem
- The budgeted maximum coverage problem
- Spanning trees with many or few colors in edge-colored graphs
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- The minimum labeling spanning trees
- Title not available (Why is that?)
- Efficient probabilistically checkable proofs and applications to approximations
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Improved low-degree testing and its applications
- Local search for the minimum label spanning tree problem with bounded color classes.
- A modified greedy heuristic for the set covering problem with improved worst case bound
- Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
- A note on the minimum label spanning tree.
- Approximating MIN 2-SAT and MIN 3-SAT
Cited In (28)
- The complexity of bottleneck labeled graph problems
- A note on the minimum label spanning tree.
- Finding disjoint paths in networks with star shared risk link groups
- Improved approximation bounds for the minimum constraint removal problem
- Sequence Hypergraphs: Paths, Flows, and Cuts
- Labeled traveling salesman problems: complexity and approximation
- On the maximum disjoint paths problem on edge-colored graphs
- Approximate tradeoffs on weighted labeled matroids
- Augmenting weighted graphs to establish directed point-to-point connectivity
- On the shared transportation problem: computational hardness and exact approach
- Sequence hypergraphs
- Labeled cuts in graphs
- The label cut problem with respect to path length and label frequency
- Complexity and approximation results on the shared transportation problem
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- On the hardness of labeled correlation clustering problem: a parameterized complexity view
- Minimum Cell Connection in Line Segment Arrangements
- A note on the clustered set covering problem
- The parameterized complexity of some minimum label problems
- Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
- Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem
- Algorithms and complexity results for labeled correlation clustering problem
- Complexity of column generation in network design with path-based survivability mechanisms
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Improved approximation bounds for the minimum constraint removal problem
- Approximation and hardness results for label cut and related problems
- The maximum labeled path problem
- Minimum label \(s\)-\(t\) cut has large integrality gaps
This page was built for publication: Approximation algorithms and hardness results for labeled connectivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2426652)
