Approximation and Hardness Results for Label Cut and Related Problems

DOI10.1007/978-3-642-02017-9_48MaRDI QIDQ3630231zbMATH OpenOpenAlexFDO

Authors Peng Zhang, Jin-Yi Cai, Lin-Qing Tang, Wen-Bo Zhao

Publication date 3 June 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02017-9_48

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

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
• The label cut problem with respect to path length and label frequency

Cited in

(12)

• Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem
• The parameterized complexity of some minimum label problems
• Maximum reachability preserved graph cut
• Minimum label \(s\)-\(t\) cut has large integrality gaps
• Approximating minimum label s-t cut via linear programming
• Labeled cuts in graphs
• The label cut problem with respect to path length and label frequency
• The maximum labeled path problem
• Efficient Algorithms for the Label Cut Problems
• Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
• The parameterized complexity of some minimum label problems
• Approximation and hardness results for label cut and related problems

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 Q3630231)