Name
Abstract | ||
|---|---|---|
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, Gamma circular-arc graphs, proper circular- arc graphs and convex-round graphs. |
Year | Venue | Keywords |
|---|---|---|
2013 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | circular-ones property,matrix isomorphism,circular-arc graphs,graph isomorphism,PC tree |
DocType | Volume | Issue |
Journal | 15.0 | 1.0 |
ISSN | Citations | PageRank |
1462-7264 | 16 | 1.01 |
References | Authors | |
21 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew R. Curtis | 1 | 792 | 77.26 |
| Min Chih Lin | 2 | 259 | 21.22 |
| R McConnell | 3 | 825 | 66.28 |
| Yahav Nussbaum | 4 | 122 | 8.59 |
| Francisco J. Soulignac | 5 | 101 | 10.56 |
| Jeremy P. Spinrad | 6 | 1342 | 115.52 |
| Jayme Luiz Szwarcfiter | 7 | 618 | 95.79 |