Computing roots of directed graphs is graph isomorphism hard

Details Computing roots of directed graphs is graph isomorphism hard Computing roots of directed graphs is graph isomorphism hard

2002-07-02

arxiv.org/abs/math/0207020v1

Mathematics

Combinatorics

15 pages, 4 figures

Scientific paper

The k-th power D^k of a directed graph D is defined to be the directed graph on the vertices of D with an arc from a to b in D^k iff one can get from a to b in D with exactly k steps. This notion is equivalent to the k-fold composition of binary relations or k-th powers of Boolean matrices. A k-th root of a directed graph D is another directed graph R with R^k = D. We show that for each k >= 2, computing a k-th root of a directed graph is at least as hard as the graph isomorphism problem.

Affiliated with

Also associated with

No associations

Rating

Computing roots of directed graphs is graph isomorphism hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing roots of directed graphs is graph isomorphism hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing roots of directed graphs is graph isomorphism hard will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-632695