Paper Info
Title
Helly Circular-Arc Graph Isomorphism Is in Logspace.
Abstract
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 trees employed in McConnell's linear time representation algorithm for interval matrices are adapted to the logspace setting and endowed with additional information to allow canonization. As a consequence, the isomorphism and recognition problems for HCA graphs turn out to be logspace complete.
Year
DOI
Venue
2013
10.1007/978-3-642-40313-2_56
Lecture Notes in Computer Science
DocType
Volume
ISSN
Conference
8087
0302-9743
Citations 
PageRank 
References 
6
0.49
14
Authors
3
Name
Order
Citations
PageRank
Johannes Köbler158046.51
Sebastian Kuhnert2366.52
Oleg Verbitsky319127.50