Search
Abstract
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.
Citations
-
1
CrossRef
-
0
Web of Science
-
1
Scopus
Authors (2)
Cite as
Full text
download paper
downloaded 23 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/s10878-015-9827-4
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
JOURNAL OF COMBINATORIAL OPTIMIZATION
no. 31,
pages 1372 - 1383,
ISSN: 1382-6905 - Language:
- English
- Publication year:
- 2016
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.1007/s10878-015-9827-4
- Verified by:
- Gdańsk University of Technology
seen 141 times
Recommended for you
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