Approximation and Hardness Results for Label Cut and Related Problems
From MaRDI portal
Publication:3630231
DOI10.1007/978-3-642-02017-9_48zbMath1241.90129MaRDI QIDQ3630231
Jin-Yi Cai, Lin-Qing Tang, Wen-Bo Zhao, Peng Zhang
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
90C35: Programming involving graphs or networks
90C27: Combinatorial optimization
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Labeled cuts in graphs, The label cut problem with respect to path length and label frequency, The parameterized complexity of some minimum label problems
