Approximation and hardness results for label cut and related problems
From MaRDI portal
(Redirected from Publication:630189)
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
- scientific article; zbMATH DE number 5485450 (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?)
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximation algorithms and hardness results for labeled connectivity problems
- Finding k Cuts within Twice the Optimal
- Formal Methods for Components and Objects
- Improved approximation for directed cut problems
- Least and most colored bases
- Local search for the minimum label spanning tree problem with bounded color classes.
- On Labeled Traveling Salesman Problems
- On the hardness of approximating Multicut and Sparsest-Cut
- On the hardness of approximating label-cover
- On the hardness of approximating minimization problems
- On the minimum label spanning tree problem
- PCP characterizations of NP: toward a polynomially-small error-probability
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Spanning trees with many or few colors in edge-colored graphs
- The budgeted maximum coverage problem
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- The labeled perfect matching in bipartite graphs
- The minimum labeling spanning trees
- Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
Cited in
(23)- Minimum label \(s\)-\(t\) cut has large integrality gaps
- Algorithms and complexity results for labeled correlation clustering problem
- Sequence Hypergraphs: Paths, Flows, and Cuts
- The parameterized complexity of some minimum label problems
- The Hardness of Metric Labeling
- Sequence hypergraphs
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Refined parameterizations for computing colored cuts in edge-colored graphs
- Hypergraph \(k\)-cut in randomized polynomial time
- Approximating minimum label \(s\)-\(t\) cut via linear programming
- Maximum reachability preserved graph cut
- Approximate tradeoffs on weighted labeled matroids
- On the hardness of labeled correlation clustering problem: a parameterized complexity view
- Efficient Algorithms for the Label Cut Problems
- The parameterized complexity of some minimum label problems
- Approximation algorithms and hardness results for labeled connectivity problems
- Labeled cuts in graphs
- The label cut problem with respect to path length and label frequency
- Approximation and Hardness Results for Label Cut and Related Problems
- The maximum labeled path problem
- 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 for a class of combinatorial optimization problems with labelling
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)
