Parameterized Algorithms for Queue Layouts

作     者：Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin 

作者机构： Bruxelles Belgium Algorithms and Complexity Group TU Wien Vienna Austria Engineering Department University of Perugia Perugia Italy 

出 版 物：《Journal of Graph Algorithms and Applications》 (J. Graph Algorithms and Appl.)

年 卷 期：2022年第26卷第3期

页      面：335-352页

核心收录：

学科分类：07[理学] 0714[理学-统计学（可授理学、经济学学位）] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：A preliminary version of this paper appeared in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020) . Research of Fabrizio Montecchiani partially supported by: (i) MIUR, under grant 20174LF3T8 \u201CAHeAD: efficient Algorithms for HArnessing networked Data\u201D (ii) Dipartimento di Ingegneria dell\u2019Universit\u00E0 degli Studi di Perugia, under grants RICBA19FM and RICBA20ED. Robert Ganian acknowledges support from the Austrian Science Fund (FWF) grant Y 1329, Sujoy Bhore and Martin N\u00F6llenburg acknowledge support from FWF grant P 31119 

主　　题：Parameter estimation 

摘      要：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. © 2022, Brown University. All rights reserved.