A disjoint vertex cycle cover can be found by a perfect matching on the bipartite graph constructed from the original graph (L) and its copy (R) and with L original graph edges replaced by corresponding L-> R edges.

Is it possible then to find the Hamiltonian cycle as a single cycle which as the vertex-disjoint cycle cover using a bipartite graph matching algorithm?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.