On the isomorphism problem for Helly circular-arc graphs

DOI: 10.1016/j.ic.2016.01.006

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.

DOI: 10.1007/978-3-642-40313-2_56

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.