Artykuł w czasopiśmie
Brak miniatury
Licencja

ClosedAccessDostęp zamknięty
 

Polynomial Treedepth Bounds in Linear Colorings

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:51:24Z
dc.abstract.enLow-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice. We introduce p-linear colorings as an alternative to the commonly used p-centered colorings. They can be efficiently computed in bounded expansion classes and use at most as many colors as p-centered colorings. Although a set of k<p colors from a p-centered coloring induces a subgraph of treedepth at most k, the same number of colors from a p-linear coloring may induce subgraphs of larger treedepth. We establish a polynomial upper bound on the treedepth in general graphs, and give tighter bounds in trees and interval graphs via constructive coloring algorithms. We also give a co-NP-completeness reduction for recognizing p-linear colorings and discuss ways to overcome this limitation in practice.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorKun, Jeremy
dc.contributor.authorPilipczuk, Marcin
dc.contributor.authorSullivan, Blair D.
dc.contributor.authorO’Brien, Michael P.
dc.date.accessioned2024-01-25T17:02:39Z
dc.date.available2024-01-25T17:02:39Z
dc.date.issued2020
dc.description.financePublikacja bezkosztowa
dc.description.number1
dc.description.volume83
dc.identifier.doi10.1007/S00453-020-00760-0
dc.identifier.issn0178-4617
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/116479
dc.identifier.weblinkhttps://link.springer.com/content/pdf/10.1007/s00453-020-00760-0.pdf
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofAlgorithmica
dc.relation.pages361-386
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titlePolynomial Treedepth Bounds in Linear Colorings
dc.typeJournalArticle
dspace.entity.typePublication