Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem
From MaRDI portal
Publication:1702134
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
Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
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.