Simple view

Full metadata view

Authors

Statistics

An algorithm for finding edge span of cacti

2016
journal article
article
10.1007/s10878-015-9827-4
Journal
Journal of Combinatorial Optimization
25
Author
Janczewski Robert

Turowski Krzysztof
Volume
31
Issue
4
Pages
1373--1382
ISSN
1382-6905
eISSN
1573-2886
Keywords in English

cacti

edge span

vertex coloring

Language
English
Journal language
English
Abstract in English

Let be a nonempty graph and be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of such that: (1) ; (2) the edge span of c , i.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 in time, where n is the number of vertices of .

Affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
Scopus© citations
1
cris.lastimport.wos2024-04-10T00:07:59Z
dc.abstract.enLet $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.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.contributor.authorJanczewski, Robertpl
dc.contributor.authorTurowski, Krzysztof - 425506 pl
dc.date.accessioned2021-08-26T08:01:04Z
dc.date.available2021-08-26T08:01:04Z
dc.date.issued2016pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number4pl
dc.description.physical1373--1382pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume31pl
dc.identifier.doi10.1007/s10878-015-9827-4pl
dc.identifier.eissn1573-2886pl
dc.identifier.issn1382-6905pl
dc.identifier.projectDEC-2011/02/A/ST6/00201pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/277542
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl*
dc.share.typeinne
dc.subject.encactipl
dc.subject.enedge spanpl
dc.subject.envertex coloringpl
dc.subtypeArticlepl
dc.titleAn $O(n log n)$ algorithm for finding edge span of cactipl
dc.title.journalJournal of Combinatorial Optimizationpl
dc.typeJournalArticlepl
dspace.entity.typePublication
cris.lastimport.wos
2024-04-10T00:07:59Z
dc.abstract.enpl
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$.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.contributor.authorpl
Janczewski, Robert
dc.contributor.authorpl
Turowski, Krzysztof - 425506
dc.date.accessioned
2021-08-26T08:01:04Z
dc.date.available
2021-08-26T08:01:04Z
dc.date.issuedpl
2016
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
4
dc.description.physicalpl
1373--1382
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
31
dc.identifier.doipl
10.1007/s10878-015-9827-4
dc.identifier.eissnpl
1573-2886
dc.identifier.issnpl
1382-6905
dc.identifier.projectpl
DEC-2011/02/A/ST6/00201
dc.identifier.projectpl
ROD UJ / OP
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/277542
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa
dc.rights.licence
CC-BY
dc.rights.uri*
http://creativecommons.org/licenses/by/4.0/legalcode.pl
dc.share.type
inne
dc.subject.enpl
cacti
dc.subject.enpl
edge span
dc.subject.enpl
vertex coloring
dc.subtypepl
Article
dc.titlepl
An $O(n log n)$ algorithm for finding edge span of cacti
dc.title.journalpl
Journal of Combinatorial Optimization
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations
No affiliation
Janczewski, Robert
Turowski, Krzysztof

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
10
Views per month
Views per city
Ashburn
3
Wroclaw
2
Dublin
1
Warsaw
1
Downloads
janczewski_turowski_an_$O(n log n)$_algorithm_for_finding_2016.pdf
2

Open Access

Thumbnail Image
License
CC-BY

Except as otherwise noted, this item is licensed under : Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa

Collections
Research publications
Exact sciences
ROD UJ