Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace
复制标题
解决对数空间中适当圆弧图的规范表示和星系统问题
DOI：
10.1016/j.jda.2016.03.001
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
O. Verbitsky
中科院分区：
文献类型：
--
作者：
J. Köbler;S. Kuhnert;O. Verbitsky
我们提出了一个对数空间算法，构造一个典型的交叉模型，为一个给定的适当的圆弧图，其中典型的意思是同构图接收相同的模型。这意味着这些图的识别和同构问题在对数空间中是可解的。对于更广泛的一类凹圆图，它仍然拥有（不一定是正确的）圆弧模型，我们表明，一个规范的圆弧模型也可以在对数空间中构建。作为这些结果的基石，我们设计了一个计算圆弧超图的规范圆弧模型的对数空间算法。这类超图对应于具有圆1性质的矩阵，在计算基因组学中起着重要的作用。我们的结果意味着存在一个判断给定矩阵是否具有此性质的对数空间算法。此外，我们考虑了由闭邻域超图重构图的星星系统问题。我们证明了这个问题是可解的对数空间的类适当的圆弧，凹圆，和co-convex graphs.Note，在对数空间中解决的问题意味着它是可解的类AC 1的并行算法。对于所考虑的问题，最多的AC 2算法是已知的。
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, wherecanonicalmeans that isomorphic graphs receive identical models. This implies that the recognition and the isomorphism problems for these graphs are solvable in logspace. For the broader class of concave-round graphs, which still possess (not necessarily proper) circular-arc models, we show that a canonical circular-arc model can also be constructed in logspace. As a building block for these results, we design a logspace algorithm for computing canonical circular-arc models of circular-arc hypergraphs. This class of hypergraphs corresponds to matrices with thecircular ones property, which play an important role in computational genomics. Our results imply that there is a logspace algorithm that decides whether a given matrix has this property.Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.Note that solving a problem in logspace implies that it is solvable by a parallel algorithm of the class AC1. For the problems under consideration, at most AC2algorithms were known earlier.
登录
查看更多内容
Le Probleme detiles pour graphes est np-complete
DOI：
10.1016/0012-365x(81)90271-5
发表时间：
1981
期刊：
Discret. Math.
影响因子：
--
作者：
Francoise Lalonde
通讯作者：
Francoise Lalonde
关于从恒星系统重建无 H 图的复杂性
影响因子：
0.9
作者：
F. Fomin;Jan Kratochvíl;D. Lokshtanov;Federico Mancini;J. A. Telle
通讯作者：
J. A. Telle
DOI：
--
发表时间：
2014
期刊：
arXiv.org
影响因子：
--
作者：
Francisco J. Soulignac
通讯作者：
Francisco J. Soulignac
影响因子：
0.8
作者：
J. Bang;Jing Huang;Anders Yeo
通讯作者：
Anders Yeo
DOI：
10.1145/62.322436
发表时间：
1984
期刊：
J. ACM
影响因子：
--
作者：
J. Reif
通讯作者：
J. Reif