An O ( n log n ) algorithm for finding edge span of cacti - Publikacja - MOST Wiedzy

Wyszukiwarka

An O ( n log n ) algorithm for finding edge span of cacti

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

  • 0
    CrossRef
  • 0
    Web of Science
  • 0
    Scopus

Robert Janczewski, Krzysztof Turowski. (2016). An O ( n log n ) algorithm for finding edge span of cacti, 31(4), 1372-1383. https://doi.org/10.1007/s10878-015-9827-4

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

wyświetlono 13 razy

Publikacje, które mogą cię zainteresować

Meta Tagi