Approximation and hardness results for label cut and related problems
From MaRDI portal
Publication:630189
DOI10.1007/S10878-009-9222-0zbMATH Open1211.90201OpenAlexW2016115187MaRDI QIDQ630189FDOQ630189
Lin-Qing Tang, Wen-Bo Zhao, Jin-Yi Cai, Peng Zhang
Publication date: 17 March 2011
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.113.6742
Recommendations
- Approximation and Hardness Results for Label Cut and Related Problems
- Efficient Algorithms for the Label Cut Problems
- Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem
- Labeled cuts in graphs
- Approximating minimum label \(s\)-\(t\) cut via linear programming
Cites Work
- Title not available (Why is that?)
- The labeled perfect matching in bipartite graphs
- On the minimum label spanning tree problem
- The budgeted maximum coverage problem
- On the hardness of approximating Multicut and Sparsest-Cut
- Spanning trees with many or few colors in edge-colored graphs
- On the hardness of approximating minimization problems
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- The minimum labeling spanning trees
- Approximation algorithms and hardness results for labeled connectivity problems
- Title not available (Why is that?)
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Finding k Cuts within Twice the Optimal
- Primal-dual approximation algorithms for integral flow and multicut in trees
- On the hardness of approximating label-cover
- Improved approximation for directed cut problems
- Local search for the minimum label spanning tree problem with bounded color classes.
- Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
- Least and most colored bases
- Title not available (Why is that?)
- On Labeled Traveling Salesman Problems
- Formal Methods for Components and Objects
- PCP characterizations of NP: toward a polynomially-small error-probability
Cited In (16)
- Maximum cuts in edge-colored graphs
- Approximation and Hardness Results for Label Cut and Related Problems
- Hypergraph \(k\)-cut in randomized polynomial time
- Sequence Hypergraphs: Paths, Flows, and Cuts
- Approximate tradeoffs on weighted labeled matroids
- Efficient Algorithms for the Label Cut Problems
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- On the hardness of labeled correlation clustering problem: a parameterized complexity view
- Sequence Hypergraphs
- Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
- Refined parameterizations for computing colored cuts in edge-colored graphs
- Secluded 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
- Algorithms and complexity for a class of combinatorial optimization problems with labelling
- Minimum label \(s\)-\(t\) cut has large integrality gaps
This page was built for publication: Approximation and hardness results for label cut and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q630189)
