Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones

Details Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones

2001-06-19

arxiv.org/abs/cs/0106041v1

Computer Science

Computational Complexity

12 pages, appears as part of a ICTCS 2001 paper of the same authors

Scientific paper

We prove that computing a single pair of vertices that are mapped onto each other by an isomorphism $\phi$ between two isomorphic graphs is as hard as computing $\phi$ itself. This result optimally improves upon a result of G\'{a}l et al. We establish a similar, albeit slightly weaker, result about computing complete Hamiltonian cycles of a graph from partial Hamiltonian cycles.

Affiliated with

Also associated with

No associations

Rating

Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones 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 Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-645703