Abstract
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.
The first author was supported by Ministry of Education, Science, Sports and Culture of Japan as Oversea's Research Scholar. The third author was supported by the Foundation for Computer Science (S.I.O.N) of the Netherlands Organization for Scientific Research (N.W.O.). The last author was supported by the Training and Mobility of Researchers (TMR) Program, (EU contract no ERBFMBICT950198).
This is a preview of subscription content, log in via an institution.
Preview
Unable to display preview. Download preview PDF.
References
H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Technical Report UU-CS-1996-02, Dept. of Computer Science, Utrecht University, The Netherlands.
H. L. Bodlaender, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms, 11 (1990), pp. 631–643.
F. R. K. Chung and P. D. Seymour, Graphs with small bandwidth and cutwidth, Discrete Math., 75 (1989), pp. 113–119.
C. J. Colbourn and K. S. Booth. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput., 10 (1981), pp. 203–225.
R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness I: Basic Results, SIAM J. Comput., 24 (1995), pp. 873–921.
R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness II: On completeness for W[1], Theor. Comput. Sci. 141 (1995), pp. 109–131.
L. S. Filotti and J. N. Mayer, A polynomial time algorithm for determining the isomorphism of graphs of fixed genus, Proc. 12th Ann. ACM Symp. Theory of Computing, Los Angeles (1980), pp. 236–243.
E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, JCSS, 25 (1982), pp. 42–65.
G. L. Miller, Isomorphism testing for graphs of bounded genus, Proc. 12th Ann. ACM Symp. Theory of Computing, Los Angeles (1980), pp. 225–235.
D. Seese, Tree-partite graphs and the complexity of algorithms, Proc. Int. Conf. on Fundamentals of Computation Theory, LNCS 199, (1985), pp. 412–421.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yamazaki, K., Bodlaender, H.L., de Fluiter, B., Thilikos, D.M. (1997). Isomorphism for graphs of bounded distance width. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds) Algorithms and Complexity. CIAC 1997. Lecture Notes in Computer Science, vol 1203. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62592-5_79
Download citation
DOI: https://doi.org/10.1007/3-540-62592-5_79
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62592-6
Online ISBN: 978-3-540-68323-0
eBook Packages: Springer Book Archive