Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem

DOI10.1007/s00453-016-0265-1zbMath1386.68224OpenAlexW2566743541MaRDI QIDQ1702134

Peng Zhang, Bin Fu, Lin-Qing Tang

Publication date: 28 February 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0265-1

zbMATH Keywords

shortest pathminimum cutapproximation algorithmslabel cut

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Minimum label \(s\)-\(t\) cut has large integrality gaps, Maximum cuts in edge-colored graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Approximation and hardness results for label cut and related problems
• Discrete particle swarm optimization for the minimum labelling Steiner tree problem
• The labeled perfect matching in bipartite graphs
• Approximation algorithms for combinatorial problems
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• The budgeted maximum coverage problem
• Labeled traveling salesman problems: complexity and approximation
• The parameterized complexity of some minimum label problems
• Approximation algorithms and hardness results for labeled connectivity problems
• Approximating Minimum Label s-t Cut via Linear Programming
• The Colorful Traveling Salesman Problem
• Spanning trees with many or few colors in edge-colored graphs
• Formal Methods for Components and Objects
• Combinatorial optimization. Theory and algorithms.