Author： Babel L. Ponomarenko I.N. Tinhofer G.
Publisher： Academic Press
ISSN： 0196-6774
Source： Journal of Algorithms, Vol.21, Iss.3, 1996-11, pp. : 542-564
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
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.
Related content
Access to resources
Recommend
Realization of Matrices and Directed Graphs
By Motwani R.
Journal of Algorithms, Vol. 27, Iss. 1, 1998-04 ,pp. :
Covering directed graphs by in-trees
By Kamiyama Naoyuki Katoh Naoki
Journal of Combinatorial Optimization, Vol. 21, Iss. 1, 2011-01 ,pp. :
Isomorphisms of algebras associated with directed graphs
Mathematische Annalen, Vol. 330, Iss. 4, 2004-12 ,pp. :