Restricted space algorithms for isomorphism on bounded treewidth graphs

Show simple item record Das, Bireswar Toran, Jacobo Wagner, Fabian 2014-03-16T11:24:34Z 2014-03-16T11:24:34Z 2012-08
dc.identifier.citation Das, Bireswar; Torán, J. and Wagner, F., “Restricted space algorithms for isomorphism on bounded treewidth graphs”, Information and Computation, DOI: 10.1016/j.ic.2012.05.003, vol. 217, pp. 71–83, Aug. 2012. en_US
dc.identifier.issn 0890-5401
dc.description.abstract The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following results: • Isomorphism for bounded tree distance width graphs is in L and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace. • For bounded treewidth graphs, when both input graphs are given together with a tree decomposition, the problem of whether there is an isomorphism which respects the decompositions (i.e. when only isomorphisms are considered, mapping bags in one decomposition blockwise onto bags in the other decomposition) is in L. • For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in LogCFL. • As a corollary the isomorphism problem for bounded treewidth graphs is in LogCFL. This improves the known TC1 upper bound for the problem given by Grohe and Verbitsky. en_US
dc.description.statementofresponsibility by Bireswar Dasa, Jacobo Toránb and Fabian Wagne
dc.format.extent Vol. 217, pp. 71–83
dc.language.iso en en_US
dc.publisher Elsevier en_US
dc.subject Algorithms en_US
dc.subject Complexity en_US
dc.subject Graph Isomorphism problem en_US
dc.subject Treewidth en_US
dc.title Restricted space algorithms for isomorphism on bounded treewidth graphs en_US
dc.type Article en_US
dc.relation.journal Information and Computation

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account