The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs |
| |
Authors: | L Babel I N Ponomarenko G Tinhofer |
| |
Institution: | aInstitute of Mathematics, Technical University of Munich, D-80290, Munich, Germany;bPOMI, Fontanka 27, 191011, Saint Petersburg, Russia |
| |
Abstract: | This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path graphs is isomorphism complete, whereas for rooted directed path graphs we present a polynomial-time isomorphism algorithm. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|