Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-043 | 19th July 2010 18:14

Interval Graphs: Canonical Representations in Logspace

RSS-Feed




Revision #1
Authors: Sebastian Kuhnert, Johannes Köbler, Bastian Laubner, Oleg Verbitsky
Accepted on: 19th July 2010 18:14
Downloads: 3349
Keywords: 


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 a logspace algorithm computing their canonical representations by proper and by unit interval systems.



Changes to previous version:

The main result is now stated in the interval hypergraph setting, yielding also canonization of convex graphs. The hardness results are extended to interval hypergraphs and convex graphs as well. Finally, we also show how to compute proper and unit interval representations in logspace.


Paper:

TR10-043 | 5th March 2010 18:35

Interval Graphs: Canonical Representation in Logspace





TR10-043
Authors: Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
Publication: 12th March 2010 12:11
Downloads: 2369
Keywords: 


Abstract:

We present a logspace algorithm for computing a canonical interval representation and a canonical labeling of interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.



ISSN 1433-8092 | Imprint