Isomorphism of graph classes related to the circular-ones property
Isomorphism of graph classes related to the circular-ones property
复制标题
与circular-ones属性相关的图类同构
DOI：
10.46298/dmtcs.625
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
J. Szwarcfiter
中科院分区：
文献类型：
--
作者：
Andrew R. Curtis;Min Chih Lin;R. McConnell;Yahav Nussbaum;Francisco J. Soulignac;J. Spinrad;J. Szwarcfiter
我们给出了一个线性时间算法，检查两个0-1矩阵之间的同构，服从循环1属性。我们的算法是类似的同构算法的Lueker和Booth的区间图，但PC树，这是无根的，有一个循环的性质，而不是PQ树，这是根。该算法导出了相关图类的线性时间同构算法，包括Helly圆弧图、Γ圆弧图、真圆弧图和凸圆图。
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. Our algorithm is similar to the isomorphism algorithm for interval graphs of Lueker and Booth, but works on PC trees, which are unrooted and have a cyclic nature, rather than with PQ trees, which are rooted. This algorithm leads to linear-time isomorphism algorithms for related graph classes, including Helly circular-arc graphs, Γ circular-arc graphs, proper circular-arc graphs and convex-round graphs.
解决对数空间中适当圆弧图的规范表示和星系统问题
DOI：
10.1016/j.jda.2016.03.001
发表时间：
2016
期刊：
影响因子：
--
作者：
J. Köbler;S. Kuhnert;O. Verbitsky
通讯作者：
O. Verbitsky
区间图：对数空间中的规范表示
DOI：
10.1137/10080395x
发表时间：
2011
期刊：
SIAM J. Comput.
影响因子：
--
作者：
J. Köbler;S. Kuhnert;B. Laubner;O. Verbitsky
通讯作者：
O. Verbitsky