Abstract | ||
---|---|---|
The Graph Isomorphism problem restricted to graphs of bounded treewidth or
bounded tree distance width are known to be solvable in polynomial time
[Bod90],[YBFT99]. 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. considering only isomorphisms 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
[GroVer06]. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.ic.2012.05.003 | Symposium on Theoretical Aspects of Computer Science |
Keywords | DocType | Volume |
bounded treewidth,bounded treewidth graph,following result,graph isomorphism problem,restricted space algorithm,bounded tree distance width,isomorphism problem,decomposition blockwise,mapping bag,input graph,tree decomposition,polynomial time,graph isomorphism,upper bound | Journal | 217, |
ISSN | Citations | PageRank |
0890-5401 | 7 | 0.46 |
References | Authors | |
18 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bireswar Das | 1 | 66 | 10.61 |
Jacobo Torán | 2 | 564 | 49.26 |
Fabian Wagner | 3 | 21 | 1.89 |