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)-Edge-Labelling was only partially classified in the literature. We complete this study for all p, q≥ 0 by showing that whenever (p, q) ≠ (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.
| Original language | English |
|---|---|
| Pages (from-to) | 3406-3429 |
| Number of pages | 24 |
| Journal | Algorithmica |
| Volume | 85 |
| Issue number | 11 |
| Early online date | 13 Apr 2023 |
| DOIs | |
| Publication status | Published - 1 Nov 2023 |
Bibliographical note
Funding Information:An extended abstract of this paper, omitting numerous proofs, appeared at The 16th International Conference and Workshops on Algorithms and Computation (WALCOM) 2022 [1 ].
Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
Keywords
- Colouring
- Computational complexity
- Dichotomy
- L(p, q)-labeling
- NP-hard
Fingerprint
Dive into the research topics of 'The Complexity of L(p, q)-Edge-Labelling'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver