Minimal and short representations of unit interval and unit circular-arc graphs
Minimal and short representations of unit interval and unit circular-arc graphs
复制标题
单位区间和单位圆弧图的最小和简短表示
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Francisco J. Soulignac
中科院分区：
文献类型：
--
作者：
Francisco J. Soulignac
我们考虑单位区间（UIG）和单位圆弧（UCA）图的无限制、最小和有界表示问题。在无限制版本中，给出了适当的圆弧（PCA）模型$\cal M$，目标是获得等效的UCA模型$\cal U$。我们展示了一种具有否定证明的线性时间算法，该算法也可以在日志空间中运行。在有界版本中，$\cal M$ 与$\cal U$ 的起始点必须满足的一些下限和上限一起给出。我们针对这个问题开发了一个线性空间 $O(n^2)$ 时间算法。最后，在最小版本中，圆的周长和 $\cal U$ 中的弧长必须同时尽可能最小。我们证明每个 UCA 图都承认这样一个最小模型，并给出了一个多项式时间算法来找到它。我们还考虑 UIG 图的最小表示问题。作为一个糟糕的结果，我们表明之前的线性时间算法无法为某些输入图提供最小模型。我们修复了这个算法，但不幸的是，它在线性空间中运行 $O(n^2)$ 时间。最后，我们应用最小表示算法来分别找到包含给定 UIG 和 UCA 模型的路径和循环的最小幂。
We consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version, a proper circular-arc (PCA) model $\cal M$ is given and the goal is to obtain an equivalent UCA model $\cal U$. We show a linear time algorithm with negative certification that can also be implemented to run in logspace. In the bounded version, $\cal M$ is given together with some lower and upper bounds that the beginning points of $\cal U$ must satisfy. We develop a linear space $O(n^2)$ time algorithm for this problem. Finally, in the minimal version, the circumference of the circle and the length of the arcs in $\cal U$ must be simultaneously as minimum as possible. We prove that every UCA graph admits such a minimal model, and give a polynomial time algorithm to find it. We also consider the minimal representation problem for UIG graphs. As a bad result, we show that the previous linear time algorithm fails to provide a minimal model for some input graphs. We fix this algorithm but, unfortunately, it runs in linear space $O(n^2)$ time. Finally, we apply the minimal representation algorithms so as to find the minimum powers of paths and cycles that contain a given UIG and UCA models, respectively.