*BibTeX*

@Article{KKV16hca, author = {Johannes Köbler and Sebastian Kuhnert and Oleg Verbitsky}, title = {On the isomorphism problem for {Helly} circular-arc graphs}, journal = {Information and Computation}, year = 2016, volume = 247, month = 4, pages = {266-277}, issn = {0890-5401}, doi = {10.1016/j.ic.2016.01.006}, }

**On the isomorphism problem for
Helly circular-arc graphs.**

With Johannes
Köbler, Oleg
Verbitsky.

*Information and Computation* 247:266–277 (2016)

Abstract.We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Δ trees employed in McConnell’s linear time representation algorithm for interval matrices are adapted to the logspace setting and endowed with additional information to allow canonization. As a consequence, the isomorphism and recognition problems for HCA graphs turn out to be logspace complete.

*BibTeX*

@InProceedings{KKV13hca, author = {Johannes Köbler and Sebastian Kuhnert and Oleg Verbitsky}, title = {Helly Circular-Arc Graph Isomorphism is in logspace}, booktitle = {Proc. 38th MFCS}, pages = {631-642}, year = 2013, editor = {Krishnendu Chatterjee and Jiri Sgall}, series = {LNCS}, number = 8087, publisher = {Springer}, address = {Berlin}, isbn = {978-3-642-40312-5}, doi = {10.1007/978-3-642-40313-2_56}, }

Conference version:

**Helly Circular-Arc Graph Isomorphism is in
logspace**

With Johannes
Köbler, Oleg
Verbitsky.

*Mathematical Foundations of Computer Science* (Proceedings
of 38th MFCS). Springer,
2013. Pp. 631–642.