Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs

Source
Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics
ISSN
03029743
Date Issued
2015-01-01
Author(s)
Enduri, Murali Krishna
Vinod Reddy, I.
DOI
Volume
8973
Abstract
We give a deterministic logspace algorithm for the graph isomorphism problem for graphs with bounded tree-depth. We also show that the graph isomorphism problem is fixed parameter tractable for a related parameterized graph class where the graph parameter is the length of the longest cycle.
Unpaywall
URI