HackerPapers

arXiv:1305.5976cs.DS

A Polynomial Time Algorithm for the Hamilton Circuit Problem

Xinwen Jiang

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from May 2013 to May 2013. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.