Chandoo, Maurice
Deciding CircularArc Graph Isomorphism in Parameterized Logspace
Abstract
We compute a canonical circulararc representation for a given circulararc (CA) graph which implies solving the isomorphism and recognition problem for this class. To accomplish this we split the class of CA graphs into uniform and nonuniform ones and employ a generalized version of the argument given by Köbler et al. (2013) that has been used to show that the subclass of Helly CA graphs can be canonized in logspace. For uniform CA graphs our approach works in logspace and in addition to that Helly CA graphs are a strict subset of uniform CA graphs. Thus our result is a generalization of the canonization result for Helly CA graphs. In the nonuniform case a specific set Omega of ambiguous vertices arises. By choosing the parameter k to be the cardinality of Omega this obstacle can be solved by brute force. This leads to an O(k + log(n)) space algorithm to compute a canonical representation for nonuniform and therefore all CA graphs.
BibTeX  Entry
@InProceedings{chandoo:LIPIcs:2016:5727,
author = {Maurice Chandoo},
title = {{Deciding CircularArc Graph Isomorphism in Parameterized Logspace}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {26:126:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5727},
URN = {urn:nbn:de:0030drops57275},
doi = {10.4230/LIPIcs.STACS.2016.26},
annote = {Keywords: graph isomorphism, canonical representation, parameterized algorithm}
}
2016
Keywords: 

graph isomorphism, canonical representation, parameterized algorithm 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Issue date: 

2016 
Date of publication: 

2016 