E-resources
PDF-
KÖBLER, Johannes; KUHNERT, Sebastian; LAUBNER, Bastian; VERBITSKY, Oleg
SIAM journal on computing, 01/2011, Volume: 40, Issue: 5Journal Article
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.
