Interval Graphs: Canonical Representations in Logspace
Interval Graphs: Canonical Representations in Logspace
复制标题
区间图：对数空间中的规范表示
DOI：
10.1137/10080395x
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
O. Verbitsky
中科院分区：
文献类型：
--
作者：
J. Köbler;S. Kuhnert;B. Laubner;O. Verbitsky
我们提出了一个对数空间算法计算一个典型的标签，事实上，一个典型的区间表示，区间图。为了实现这一点，我们计算区间超图的规范区间表示。这种方法也产生了一个典型的凸图的标签。因此，这些图类的同构和自同构问题在对数空间中是可解的。对于适当的区间图，我们还设计了对数空间算法计算其规范表示的适当和单位区间系统。
We present a logspace algorithm for computing a canonical labeling, in fact, a canonical interval representation, for interval graphs. To achieve this, we compute canonical interval representations of interval hypergraphs. This approach also yields a canonical labeling of convex graphs. As a consequence, the isomorphism and automorphism problems for these graph classes are solvable in logspace. For proper interval graphs we also design logspace algorithms computing their canonical representations by proper and by unit interval systems.
登录
查看更多内容
捕获区间图上的多项式时间
DOI：
10.1109/lics.2010.42
发表时间：
2010
期刊：
2010 25th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
B. Laubner
通讯作者：
B. Laubner
DOI：
10.1007/978-3-540-77891-2_3
发表时间：
2008
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Ryuhei Uehara
通讯作者：
Ryuhei Uehara
用于识别弦可比图和区间图的快速而简单的算法
DOI：
10.1137/s0097539792224814
发表时间：
1999
期刊：
SIAM J. Comput.
影响因子：
--
作者：
W. Hsu;T. Ma
通讯作者：
T. Ma
DOI：
10.1145/62.322436
发表时间：
1984
期刊：
J. ACM
影响因子：
--
作者：
J. Reif
通讯作者：
J. Reif
DOI：
10.1109/71.491584
发表时间：
1996
期刊：
IEEE Trans. Parallel Distributed Syst.
影响因子：
--
作者：
Lin Chen
通讯作者：
Lin Chen