TY - GEN
T1 - Isomorphism for graphs of bounded distance width
AU - Yamazaki, Koichi
AU - Bodlaender, Hans L.
AU - de Fluiter, Babette
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.
PY - 1997
Y1 - 1997
N2 - In this paper, we study the Graph Isomorphism problem on graphs of bounded treewidth, bounded degree or bounded bandwidth. There are O(n c) algorithms which solve Graph Isomorphism on graphs which have a bound on the treewidth, degree or bandwidth, but the exponent c depends on this bound, where n is the number of vertices in input graphs. We introduce some new graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve Graph Isomorphism in O(n 2) time for graphs with bounded rooted path distance width, and in O(n 3) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is a NP-complete problem even if the input graphs are restricted to the class of trees. Moreover we show that the rooted path or tree distance width can be computed in O(ne) time and both path and tree distance width can be computed in O(n k+1) time, when they are bounded by a constant k, where e is the number of edges in input graphs. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters.
AB - In this paper, we study the Graph Isomorphism problem on graphs of bounded treewidth, bounded degree or bounded bandwidth. There are O(n c) algorithms which solve Graph Isomorphism on graphs which have a bound on the treewidth, degree or bandwidth, but the exponent c depends on this bound, where n is the number of vertices in input graphs. We introduce some new graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve Graph Isomorphism in O(n 2) time for graphs with bounded rooted path distance width, and in O(n 3) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is a NP-complete problem even if the input graphs are restricted to the class of trees. Moreover we show that the rooted path or tree distance width can be computed in O(ne) time and both path and tree distance width can be computed in O(n k+1) time, when they are bounded by a constant k, where e is the number of edges in input graphs. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters.
UR - http://www.scopus.com/inward/record.url?scp=21744436335&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=21744436335&partnerID=8YFLogxK
U2 - 10.1007/3-540-62592-5_79
DO - 10.1007/3-540-62592-5_79
M3 - Conference contribution
AN - SCOPUS:21744436335
SN - 3540625925
SN - 9783540625926
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 276
EP - 287
BT - Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings
A2 - Bongiovanni, Giancarlo
A2 - Bovet, Daniel Pierre
A2 - Di Battista, Giuseppe
PB - Springer Verlag
T2 - 3rd Italian Conference on Algorithms and Complexity, CIAC 1997
Y2 - 12 March 1997 through 14 March 1997
ER -