<div class="csl-bib-body">
<div class="csl-entry">Bhore, S., Ganian, R., Montecchiani, F., & Nöllenburg, M. (2022). Parameterized Algorithms for Queue Layouts. <i>Journal of Graph Algorithms and Applications</i>, <i>26</i>(3), 335–352. https://doi.org/10.7155/jgaa.00597</div>
</div>
-
dc.identifier.issn
1526-1719
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/150338
-
dc.description.abstract
An h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h sets, called queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h.
en
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)