Name
Abstract | ||
|---|---|---|
. In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth.
GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent
depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable'' polynomial
time algorithms can be established. We introduce some new and natural 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 NP-hard, but both path and tree distance width can be computed in O(n
k+1
) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/3-540-62592-5_79 | Algorithmica |
Keywords | Field | DocType |
Key words. Graph isomorphism,Fixed parameter tractability,Distance pathwidth,Distance treewidth. | Discrete mathematics,Combinatorics,Tree-depth,Graph isomorphism,Partial k-tree,Chordal graph,Tree decomposition,Treewidth,Pathwidth,1-planar graph,Mathematics | Conference |
Volume | Issue | ISSN |
24 | 2 | 1432-0541 |
ISBN | Citations | PageRank |
3-540-62592-5 | 22 | 0.79 |
References | Authors | |
17 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Koichi Yamazaki | 1 | 222 | 21.85 |
| Hans L. Bodlaender | 2 | 5699 | 375.15 |
| Babette de Fluiter | 3 | 92 | 5.63 |
| Dimitrios M. Thilikos | 4 | 1844 | 124.72 |
| HL Bodlaender | 5 | 96 | 4.42 |
| DM Thilikos | 6 | 329 | 13.35 |