Wyszukiwarka
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
Abstrakt
Given a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree graphs with connected backbones and we give a complete computational complexity classification of this problem. We present a polynomial algorithm for optimal backbone coloring for subcubic graphs with arbitrary backbones. We also prove that the backbone coloring problem for graphs with arbitrary backbones and with fixed maximum degree (at least 4) is NP-complete. Furthermore, we show that for a special case of graphs with fixed maximum degree at least 5 and λ>=4 the problem remains NP-complete even for spanning tree backbones.
Cytowania
-
2
CrossRef
-
0
Web of Science
-
2
Scopus
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
INFORMATION PROCESSING LETTERS
nr 115,
wydanie 2,
strony 232 - 236,
ISSN: 0020-0190 - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Janczewski R., Turowski K.: The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones// INFORMATION PROCESSING LETTERS. -Vol. 115, iss. 2 (2015), s.232-236
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.ipl.2014.09.018
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 129 razy
Publikacje, które mogą cię zainteresować
Minimum order of graphs with given coloring parameters
- G. Bacsó,
- P. Borowiecki,
- M. Hujter
- + 1 autorów