&nbsp;
Jagiellonian University Repository

# An $O(n log n)$ algorithm for finding edge span of cacti
 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$ pl 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$. 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