论文标题
队列布局的参数化算法
Parameterized Algorithms for Queue Layouts
论文作者
论文摘要
图$ g $的$ h $ Ququeue布局由其顶点的线性顺序和边缘分配为$ h $ queues，因此没有两个独立的队列巢的独立边缘。最低$ h $，以至于$ g $承认$ h $ quququeue布局是$ g $的队列数。我们提出了两种固定参数可处理的算法，这些算法利用图形的结构特性来计算最佳队列布局。作为我们的第一个结果，我们表明，确定图形$ g $是否具有队列数$ 1 $，并且计算相应的布局是固定参数时，当通过$ g $的treeDepepth进行参数时。然后，我们的第二个结果使用更限制的参数，即顶点封面编号来解决任意$ 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$.
