Interval graphs: Canonical representations in logspace

BibTeX

@Article{KKLV11intervalgraphs,
  author =       {Johannes Köbler and Sebastian Kuhnert and Bastian Laubner and Oleg Verbitsky},
  title =        {Interval graphs: Canonical representations in logspace},
  journal =      {SIAM Journal on Computing},
  year =         2011,
  volume =       40,
  number =       5,
  pages =        {1292-1315},
  issn =         {1501-1526},
  doi =          {10.1137/10080395X},
}

Slides

Interval graphs: Canonical representations in logspace.
With Johannes Köbler, Bastian Laubner, Oleg Verbitsky.
SIAM Journal on Computing 40(5):1292–1315 (2011).

Abstract. We present a logspace algorithm for computing a canonical labeling, in fact, a canonical interval representation, for interval graphs. To achieve this, we compute canonical interval representations of interval hypergraphs. This approach also yields a canonical labeling of convex graphs. As a consequence, the isomorphism and automorphism problems for these graph classes are solvable in logspace. For proper interval graphs we also design logspace algorithms computing their canonical representations by proper and by unit interval systems.

DOI: 10.1007/978-3-642-14165-2_33

BibTeX

@Article{KKLV10intervalgraphs,
  author =       {Johannes Köbler and Sebastian Kuhnert
                  and Bastian Laubner and Oleg Verbitsky},
  title =        {Interval graphs: Canonical representation in logspace},
  booktitle =    {Proceedings of 37th International Colloquium
                  on Automata, Languages and Programming (ICALP'10)},
  year =         2010,
  year =         {2010},
  pages =        {384-395},
  isbn =         {978-3-642-14164-5},
  doi =          {10.1007/978-3-642-14165-2_33},
}

Conference version:
Interval graphs: Canonical representation in logspace
With Johannes Köbler, Bastian Laubner, Oleg Verbitsky.
Automata, Languages and Programming (Proceedings of 37th ICALP). Springer, 2010. Pp 384–395.