Approximation algorithms and hardness results for labeled connectivity problems
From MaRDI portal
(Redirected from Publication:2426652)
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
Cites work
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 2147947 (Why is no real title available?)
- scientific article; zbMATH DE number 1445322 (Why is no real title available?)
- A General Approximation Technique for Constrained Forest Problems
- A modified greedy heuristic for the set covering problem with improved worst case bound
- A note on the minimum label spanning tree.
- A simple efficient approximation scheme for the restricted shortest path problem
- Approximating MIN 2-SAT and MIN 3-SAT
- Approximation Schemes for the Restricted Shortest Path Problem
- Approximation algorithms for combinatorial problems
- Efficient probabilistically checkable proofs and applications to approximations
- Improved low-degree testing and its applications
- Local search for the minimum label spanning tree problem with bounded color classes.
- On approximating the longest path in a graph
- On approximation algorithms for the minimum satisfiability problem
- On the hardness of approximating minimum vertex cover
- On the minimum label spanning tree problem
- On the ratio of optimal integral and fractional covers
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Spanning trees with many or few colors in edge-colored graphs
- The budgeted maximum coverage problem
- The minimum labeling spanning trees
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
Cited in
(28)- Minimum label \(s\)-\(t\) cut has large integrality gaps
- 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
- On the maximum disjoint paths problem on edge-colored graphs
- Labeled traveling salesman problems: complexity and approximation
- Sequence Hypergraphs: Paths, Flows, and Cuts
- Approximate tradeoffs on weighted labeled matroids
- Augmenting weighted graphs to establish directed point-to-point connectivity
- 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
- On the shared transportation problem: computational hardness and exact approach
- 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
- Approximation and hardness results for label cut and related problems
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Improved approximation bounds for the minimum constraint removal problem
- The maximum labeled path problem
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)
