The label cut problem with respect to path length and label frequency

DOI10.1016/j.tcs.2016.08.006zbMath1350.68159OpenAlexW2475817483MaRDI QIDQ313969

Peng Zhang, Bin Fu

Publication date: 12 September 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.08.006

zbMATH Keywords

computational complexityapproximation algorithmparameterized algorithmglobal label cutlabel \(s\)-\(t\) cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (6)

Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs ⋮ Maximum cuts in edge-colored graphs ⋮ Refined parameterizations for computing colored cuts in edge-colored graphs ⋮ Colored cut games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• The labeled perfect matching in bipartite graphs
• The directed subgraph homeomorphism problem
• Some APX-completeness results for cubic graphs
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Graph minors. XIII: The disjoint paths problem
• The parameterized complexity of some minimum label problems
• Variable neighbourhood search for the minimum labelling Steiner tree problem
• Approximation algorithms and hardness results for labeled connectivity problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Parametrized complexity theory.
• Approximating Minimum Label s-t Cut via Linear Programming
• The Colorful Traveling Salesman Problem
• Treewidth: Characterizations, Applications, and Computations
• Approximation and Hardness Results for Label Cut and Related Problems
• A new approach to the minimum cut problem
• Computing All Small Cuts in an Undirected Network
• Reducibility among Combinatorial Problems
• Efficient Algorithms for the Label Cut Problems
• On the complexity of \(k\)-SAT

This page was built for publication: The label cut problem with respect to path length and label frequency