Isomorphism of graph classes related to the circular-ones property
作者： Yahav Nussbaum , Francisco Juan Soulignac , Jayme Luiz Szwarcfiter , Min Chih Lin , Ross M. Mcconnell
DOI:
关键词:
摘要: We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices obey the circular-ones property. Our is similar to interval graphs of Lueker and Booth, but works on PC trees, which are unrooted have cyclic nature, rather than with PQ rooted. This leads algorithms related graph classes, including Helly circular-arc graphs, Γ proper convex-round graphs.
episciences.org
archives-ouvertes.fr
dmtcs.org参考文章(32)
Shih Wei-Kuan, Hsu Wen-Lian, A new planarity test Theoretical Computer Science. ,vol. 223, pp. 179- 191 ,(1999) , 10.1016/S0304-3975(98)00120-0
Ross M. McConnell, Fabien de Montgolfier, Algebraic operations on PQ trees and modular decomposition trees workshop on graph-theoretic concepts in computer science. pp. 421- 432 ,(2005) , 10.1007/11604686_37
Yahav Nussbaum, From a Circular-Arc Model to a Proper Circular-Arc Model workshop on graph-theoretic concepts in computer science. pp. 324- 335 ,(2008) , 10.1007/978-3-540-92248-3_29
Min Chih Lin, Francisco J. Soulignac, Jayme L. Szwarcfiter, A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs scandinavian workshop on algorithm theory. pp. 355- 366 ,(2008) , 10.1007/978-3-540-69903-3_32
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Jayme L. Szwarcfiter, Min Chih Lin, Ross M. McConnell, Francisco J. Soulignac, On cliques of Helly Circular-arc Graphs Electronic Notes in Discrete Mathematics. ,vol. 30, pp. 117- 122 ,(2008) , 10.1016/J.ENDM.2008.01.020
Wen-Lian Hsu, Ross M. McConnell, PC trees and circular-ones arrangements Theoretical Computer Science. ,vol. 296, pp. 99- 116 ,(2003) , 10.1016/S0304-3975(02)00435-8
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky, Interval Graphs: Canonical Representations in Logspace SIAM Journal on Computing. ,vol. 40, pp. 1292- 1315 ,(2011) , 10.1137/10080395X
Lin Chen, Graph isomorphism and identification matrices: parallel algorithms IEEE Transactions on Parallel and Distributed Systems. ,vol. 7, pp. 308- 319 ,(1996) , 10.1109/71.491584
J. Spinrad, Recognition of circle graphs Journal of Algorithms. ,vol. 16, pp. 264- 282 ,(1994) , 10.1006/JAGM.1994.1012