Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-074 | 9th May 2013 11:11

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 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.

ISSN 1433-8092 | Imprint