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

Publications

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

Author : Dr Murali Krishna Enduri

Year : 2015

Publisher : Springer Verlag

Source Title : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Document Type : Conference paper

Link

DOI

https://doi.org/10.1007/978-3-319-15612-5_30

Web

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84923673320&origin=inward

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.