The Complexity of L(p,q)-Edge-Labelling

Berthe, G.; Martin, B.; Paulusma, D.; Smith, S.

Abstract

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.

Citation

Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022, March). The Complexity of L(p,q)-Edge-Labelling. Presented at The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021), University of Jember, East Java

• Presentation Conference Type: Conference Paper (published)
• Conference Name: The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021)
• Start Date: Mar 24, 2022
• End Date: Mar 26, 2022
• Acceptance Date: Nov 20, 2021
• Online Publication Date: Mar 16, 2022
• Publication Date: 2022
• Deposit Date: Dec 20, 2021
• Publicly Available Date: Mar 16, 2023
• Print ISSN: 0302-9743
• Volume: 13174
• Pages: 175-186
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743,1611-3349
• Book Title: WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings
• ISBN: 978-3-030-96730-7
• DOI: https://doi.org/10.1007/978-3-030-96731-4_15
• Public URL: https://durham-repository.worktribe.com/output/1137274