Berthe, G. and Martin, B. and Paulusma, D. and Smith, S. (2022) 'The Complexity of L(p,q)-Edge-Labelling.', The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021) University of Jember, East Java, 24-26 Mar 2022.
The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p, q)-EdgeLabelling was only partially classified in the literature. We complete this study for all p, q ≥ 0 by showing that whenever (p, q) 6= (0, 0), the L(p, q)-Edge-Labelling problem is NP-complete. We do this by proving that for all p, q ≥ 0 except p = q = 0, there is an integer k so that L(p, q)-Edge-k-Labelling is NP-complete.
|Item Type:||Conference item (Paper)|
|Full text:||Publisher-imposed embargo |
(AM) Accepted Manuscript
File format - PDF (155Kb)
|Publisher Web site:||http://www.walcom-conference.org/upcoming.php|
|Date accepted:||20 November 2021|
|Date deposited:||20 December 2021|
|Date of first online publication:||2022|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|