Data Structures and Algorithms


A New Approach: Solving the Hamiltonian Circuit Problem in O(n2) Time in a Computer Network. (3rd. Version)

Authors: Óscar Emilio Chamizo Sánchez

Hamiltonian circuit problem (HCP for short) is one of the most famous and deeply investigated problem in computation. Given a (directed or undirected, 2 or 3 dimensional1) graph the simple goal is to answer to the question whether exists or not a circuit that visits each vertex exactly once. Since the problem of finding a Hamiltonian circuit is NP-complete, the only known way so far to find whether a general graph has a Hamiltonian circuit was to perform and exhaustive search with exponential execution time. In this paper we present an interesting supplement from our paper: "A new approach: A hardware device model solving Traveling Salesman Problem in O(n2) time. Practical application and theoretical consequences" [1] now solving any instance of HCP in O(n2) time. In section 1 we go directly to the device model and prove mathematically its validity. In section 2 we explain the basic ideas behind the model. In section 3 we analyze complexity and software and hardware design.

Comments: 6 Pages. Minor errors corrected in algorithmic design.

Download: PDF

Submission history

[v1] 2018-06-12 03:05:32
[v2] 2018-06-13 12:36:10
[v3] 2018-06-17 03:01:49

Unique-IP document downloads: 8 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus