Approximating Minimum Label s-t Cut via Linear Programming

DOI10.1007/978-3-642-29344-3_55zbMath1353.68305OpenAlexW86974874MaRDI QIDQ2894506

Peng Zhang, Lin-Qing Tang

Publication date: 29 June 2012

Published in: LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-29344-3_55

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (6)

The label cut problem with respect to path length and label frequency ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ Efficient heuristics for the minimum labeling global cut problem ⋮ Maximum cuts in edge-colored graphs ⋮ Approximate tradeoffs on weighted labeled matroids

This page was built for publication: Approximating Minimum Label s-t Cut via Linear Programming