Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with logspace completeness:
TR09-053 | 20th May 2009
Johannes Köbler, Sebastian Kuhnert

The Isomorphism Problem for k-Trees is Complete for Logspace

Revisions: 1

We show that k-tree isomorphism can be decided in logarithmic
space by giving a logspace canonical labeling algorithm. This improves
over the previous StUL upper bound and matches the lower bound. As a
consequence, the isomorphism, the automorphism, as well as the
canonization problem for k-trees ... more >>>

TR10-043 | 5th March 2010
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky

Interval Graphs: Canonical Representation in Logspace

Revisions: 1

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.

more >>>

TR13-074 | 9th May 2013
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

Helly Circular-Arc Graph Isomorphism is in Logspace

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 Delta trees employed in McConnell's linear time representation algorithm for interval matrices ... more >>>

ISSN 1433-8092 | Imprint