![]() |
Discrete Mathematics & Theoretical Computer Science |
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.
Source : ScholeXplorer
IsRelatedTo ARXIV 1903.11062 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1903.11062
|