Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

G. Berthe



Contributors

Petra Mutzel
Editor

Md. Saidur Rahman
Editor

Slamin
Editor

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). The Complexity of L(p,q)-Edge-Labelling. In P. Mutzel, M. . S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings (175-186). https://doi.org/10.1007/978-3-030-96731-4_15

Conference Name The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021)
Conference Location University of Jember, East Java
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 29, 2024
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

Files





You might also like



Downloadable Citations