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

Gaétan Berthe; Barnaby Martin; Daniël Paulusma; Siani Smith

doi:10.1007/978-3-030-96731-4_15

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

Gaétan Berthe, Barnaby Martin^*, Daniël Paulusma, Siani Smith

^*Corresponding author for this work

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

1 Citation (Scopus)

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
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings
Editors	Petra Mutzel, Md. Saidur Rahman, Slamin
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	175-186
Number of pages	12
ISBN (Electronic)	9783030967314
ISBN (Print)	9783030967307
DOIs	https://doi.org/10.1007/978-3-030-96731-4_15
Publication status	Published - 16 Mar 2022
Event	16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 - Jember, Indonesia Duration: 24 Mar 2022 → 26 Mar 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13174 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022
Country/Territory	Indonesia
City	Jember
Period	24/03/22 → 26/03/22

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-030-96731-4_15Licence: Unspecified

Handle.net

Persistent link

Cite this

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, Proceedings (pp. 175-186). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13174 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-96731-4_15

Berthe, Gaétan ; Martin, Barnaby ; Paulusma, Daniël et al. / The Complexity of L(p, q)-Edge-Labelling. WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings. editor / Petra Mutzel ; Md. Saidur Rahman ; Slamin. Springer Science and Business Media Deutschland GmbH, 2022. pp. 175-186 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a9da018b96f24f8b9747060934d85294,

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

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.",

author = "Ga{\'e}tan Berthe and Barnaby Martin and Dani{\"e}l Paulusma and Siani Smith",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 ; Conference date: 24-03-2022 Through 26-03-2022",

year = "2022",

month = mar,

day = "16",

doi = "10.1007/978-3-030-96731-4\_15",

language = "English",

isbn = "9783030967307",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "175--186",

editor = "Petra Mutzel and Rahman, \{Md. Saidur\} and Slamin",

booktitle = "WALCOM",

address = "Germany",

}

Berthe, G, Martin, B, Paulusma, D & Smith, S 2022, The Complexity of L(p, q)-Edge-Labelling. in P Mutzel, MS Rahman & Slamin (eds), WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13174 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 175-186, 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022, Jember, Indonesia, 24/03/22. https://doi.org/10.1007/978-3-030-96731-4_15

The Complexity of L(p, q)-Edge-Labelling. / Berthe, Gaétan; Martin, Barnaby; Paulusma, Daniël et al.
WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings. ed. / Petra Mutzel; Md. Saidur Rahman; Slamin. Springer Science and Business Media Deutschland GmbH, 2022. p. 175-186 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13174 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

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

AU - Berthe, Gaétan

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

PY - 2022/3/16

Y1 - 2022/3/16

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85127854332&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-96731-4_15

DO - 10.1007/978-3-030-96731-4_15

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85127854332

SN - 9783030967307

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 175

EP - 186

BT - WALCOM

A2 - Mutzel, Petra

A2 - Rahman, Md. Saidur

A2 - Slamin, null

PB - Springer Science and Business Media Deutschland GmbH

T2 - 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022

Y2 - 24 March 2022 through 26 March 2022

ER -

Berthe G, Martin B, Paulusma D, Smith S. The Complexity of L(p, q)-Edge-Labelling. In Mutzel P, Rahman MS, Slamin, editors, WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 175-186. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-96731-4_15