Jagiellonian University Repository

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

pcg.skipToMenu

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

Show full item record

dc.contributor.author Janczewski, Robert pl
dc.contributor.author Turowski, Krzysztof [SAP14041792] pl
dc.date.accessioned 2021-08-26T08:01:04Z
dc.date.available 2021-08-26T08:01:04Z
dc.date.issued 2016 pl
dc.identifier.issn 1382-6905 pl
dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/277542
dc.language eng pl
dc.rights Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa *
dc.rights.uri http://creativecommons.org/licenses/by/4.0/pl/legalcode *
dc.title An $O(n log n)$ algorithm for finding edge span of cacti pl
dc.type JournalArticle pl
dc.description.physical 1373--1382 pl
dc.abstract.en Let $G=(V,E)$ be a nonempty graph and $ξ:E→N$ 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)|≥ξ(uv) for each edge uv∈E$ ; (2) the edge span of c , i.e. $max{|c(u)−c(v)|:uv∈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(nlogn)$ time, where n is the number of vertices of $G$. pl
dc.subject.en cacti pl
dc.subject.en edge span pl
dc.subject.en vertex coloring pl
dc.description.volume 31 pl
dc.description.number 4 pl
dc.identifier.doi 10.1007/s10878-015-9827-4 pl
dc.identifier.eissn 1573-2886 pl
dc.title.journal Journal of Combinatorial Optimization pl
dc.language.container eng pl
dc.affiliation Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej pl
dc.subtype Article pl
dc.rights.original CC-BY; inne; ostateczna wersja wydawcy; w momencie opublikowania; 0 pl
dc.identifier.project DEC-2011/02/A/ST6/00201 pl
dc.identifier.project ROD UJ / OP pl
.pointsMNiSW [2016 A]: 25


Files in this item

This item appears in the following Collection(s)

Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa Except where otherwise noted, this item's license is described as Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa