Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Interval Graphs:
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 >>>

TR12-032 | 4th April 2012
Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe

Interval graph representation with given interval and intersection lengths

We consider the problem of finding interval representations of graphs that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir proved that the problem is NP-complete if only the former are given [SIAM J. Discr. ... more >>>

ISSN 1433-8092 | Imprint