Wyszukiwarka
Abstrakt
Let G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for cycles and bipartite graphs. Next, we use the last two results to construct an algorithm that solves the problem for a given cactus G in O(nlog n) time, where n is the number of vertices of G.
Cytowania
-
1
CrossRef
-
0
Web of Science
-
1
Scopus
Cytuj jako
Pełna treść
pobierz publikację
pobrano 23 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10878-015-9827-4
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
JOURNAL OF COMBINATORIAL OPTIMIZATION
nr 31,
strony 1372 - 1383,
ISSN: 1382-6905 - Język:
- angielski
- Rok wydania:
- 2016
- Opis bibliograficzny:
- Janczewski R., Turowski K.: An O ( n log n ) algorithm for finding edge span of cacti // JOURNAL OF COMBINATORIAL OPTIMIZATION. -Vol. 31, nr. 4 (2016), s.1372-1383
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10878-015-9827-4
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 139 razy
Publikacje, które mogą cię zainteresować
Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
- M. Lemańska,
- J. A. RODRíGUEZ-VELáZQUEZ,
- R. Trujillo-Rasua
2017