EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Parameterized Algorithms for Queue Layouts

Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg

Journal of Graph Algorithms and Applications · 01.06.2022 · 26 (3) · 335-352

DOI: 10.7155/jgaa.00597 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Algorithms and Applications, online erschienen am 01.06.2022. Verfasst von Sujoy Bhore und 3 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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$.

Zitieren

APA

Bhore, S., Ganian, R., Montecchiani, F., & Nöllenburg, M. (2022). Parameterized Algorithms for Queue Layouts. Journal of Graph Algorithms and Applications, 26(3), 335-352. https://doi.org/10.7155/jgaa.00597

Vancouver

Bhore S, Ganian R, Montecchiani F, Nöllenburg M. Parameterized Algorithms for Queue Layouts. Journal of Graph Algorithms and Applications. 2022;26(3):335-352. doi:10.7155/jgaa.00597

BibTeX
@article{Bhore2022,
  author = {Bhore, Sujoy and Ganian, Robert and Montecchiani, Fabrizio and Nöllenburg, Martin},
  title = {Parameterized Algorithms for Queue Layouts},
  journal = {Journal of Graph Algorithms and Applications},
  year = {2022},
  volume = {26},
  number = {3},
  pages = {335--352},
  doi = {10.7155/jgaa.00597}
}
Kostenlos starten →