Parameterized Algorithms for Queue Layouts
Parameterized Algorithms for Queue Layouts
复制标题
队列布局的参数化算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
M. Nöllenburg
中科院分区：
文献类型：
--
作者：
S. Bhore;R. Ganian;Fabrizio Montecchiani;M. Nöllenburg
图 $G$ 的 $h$ 队列布局由其顶点的线性顺序和将其边划分为 $h$ 队列组成，使得同一队列中没有两个独立的边嵌套。 $G$ 允许 $h$ 队列布局的最小 $h$ 是 $G$ 的队列号。我们提出了两种固定参数的易处理算法，它们利用图的结构特性来计算最佳队列布局。作为我们的第一个结果，我们表明，当通过 $G$ 的树深度进行参数化时，确定图 $G$ 是否具有队列号 $1$ 并计算相应的布局是固定参数易于处理的。然后，我们的第二个结果使用更具限制性的参数，即顶点覆盖数，来解决任意 $h$ 的问题。
An $h$-queue layout of a graph $G$ consists of a linear order of its vertices and a partition of its edges into $h$ 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$.
一种更快的树深度参数化算法
DOI：
10.1007/978-3-662-43948-7_77
发表时间：
2014
期刊：
影响因子：
--
作者：
Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil;Somnath Sikdar
通讯作者：
Somnath Sikdar