Scholars Central

Research articlePublished 2015

A Method to Select the Edges in the Minimum Hamiltonian Cycle

Authors: Yong Wang

Journal of Computer Science & Systems Biology

Volume 8 · Issue 5 · Pages 249–254

Ask about this article

Abstract

Select any words in the title or abstract, or press this and choose a sentence.

To find the minimum Hamiltonian cycle is the objective of traveling salesman problem (TSP) whereas it has been proven to be NP-complete. To select the right edges in the minimum Hamiltonian cycle, the frequency graph is computed with a set of optimal i-vertex paths. The number of optimal i-vertex paths is formulated according to i. In these frequency graphs, the frequencies of the edges in the minimum Hamiltonian cycle are generally bigger than the average frequency and those of most of the other edges. Before i ≤ n/2+1 for even number n and i ≤ (n ± 1)/2+1 for odd number n, the frequencies of the edges in the minimum Hamiltonian cycle increase faster than the average frequency does according to i. The frequencies on the edges and their change can be taken as the heuristic information to select the edges in the minimum Hamiltonian cycle. Two simple examples are given to show the change of the frequencies of the edges in the minimum Hamiltonian cycle. The results show that they are different from those of the other edges according to i. The results can be used as the basis to design algorithms for TSP

Ask about this article

Answers come only from this article's title, abstract and keywords, each sentence pointing to where it comes from. Your question is sent to OpenAI to write the answer. Scholars Central does not store it.

Try:

More from this journal

The newest in Journal of Computer Science & Systems Biology.

All its articles

Conferences in this field

Upcoming conferences in this field.

Follow

New articles from what you follow go into your email digest, once you agree to alert emails.

  • JournalJournal of Computer Science & Systems Biology
  • SubjectComputer Science & IT
  • BylineArticles whose byline prints “Yong Wang”

For authors and organisers

Publish, present and keep up with your field

Find the right journal for your paper and submit your manuscript.

Photo: Pexels