Name
Abstract | ||
|---|---|---|
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, then our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ic.2016.01.006 | Information and Computation |
Keywords | DocType | Volume |
Graph isomorphism,Circular-arc graphs,Helly property,Graph representation,Logarithmic space | Journal | 247 |
Issue | ISSN | Citations |
C | 0890-5401 | 1 |
PageRank | References | Authors |
0.35 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Köbler | 1 | 580 | 46.51 |
| Sebastian Kuhnert | 2 | 36 | 6.52 |
| Oleg Verbitsky | 3 | 191 | 27.50 |