arXiv Open Access 2013

A Polynomial Time Algorithm for the Hamilton Circuit Problem

Xinwen Jiang

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS

Penulis (1)

Xinwen Jiang

Format Sitasi

APA MLA BibTeX

Jiang, X. (2013). A Polynomial Time Algorithm for the Hamilton Circuit Problem. https://arxiv.org/abs/1305.5976

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2013
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓