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

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

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2023-11, Vol.85 (11), p.3406-3429
Main Authors: Berthe, Gaétan, Martin, Barnaby, Paulusma, Daniël, Smith, Siani
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Complexity
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Labeling
Mathematics of Computing
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-023-01120-4