Digital Signal Processing


Analog Computer Understanding of Hamiltonian Paths, and a Possible Digitization

Authors: Bryce Kim

This paper explores finding existence of undirected hamiltonian paths in a graph using lumped/ideal circuits, specifically low-pass filters. While other alternatives are possible, a first-order RC low-pass filter is chosen to describe the process. The paper proposes a way of obtaining time complexity for counting the number of hamiltonian paths in a graph, and then shows that the time complexity of the circuits is around $O(n \log n)$ where $n$ is the number of vertices in a graph. Because analog computation is often undesirable due to several aspects, a possible digitization scheme is proposed in this paper.

Comments: 17 Pages.

Download: PDF

Submission history

[v1] 2016-07-08 17:30:42

Unique-IP document downloads: 37 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