Paper Info
Title
Interval graphs: canonical representation in logspace
Abstract
We present a logspace algorithm for computing a canonical labeling, in fact a canonical interval representation, for interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.
Year
DOI
Venue
2010
10.1137/10080395X
international colloquium on automata, languages and programming
Keywords
DocType
Volume
unit interval system,logspace algorithm,convex graph,interval graph,canonical representation,canonical representations,canonical interval representation,interval hypergraphs,graph class,automorphism problem,interval graphs,proper interval graph,graph isomorphism,graph canonization
Conference
40
Issue
ISSN
Citations 
5
0302-9743
7
PageRank 
References 
Authors
0.49
35
4
Name
Order
Citations
PageRank
Johannes Köbler158046.51
Sebastian Kuhnert2366.52
Bastian Laubner3312.14
Oleg Verbitsky419127.50