Advanced search

Browse by subject

Browse by provider

Browse by language

Content Details
Normal View
CIP View

Polynomial solvability of $NP$-complete ...

Panyukov, Anatoly...

Free

Share this content

Polynomial solvability of $NP$-complete problems by Panyukov, Anatoly ( Author )

Content Provider	Lemonjar Open Access
Publisher	Australian National University
Publication Date	06-09-2023
Summary	${ NP}$-complete problem "Hamiltonian cycle"\ for graph $G=(V,E)$ is extended to the "Hamiltonian Complement of the Graph"\ problem of finding the minimal cardinality set $H$ containing additional edges so that graph $G=(V,E\cup H)$ is Hamiltonian. The solving of "Hamiltonian Complement of a Graph"\ problem is reduced to the linear programming problem {\bf P}, which has an optimal integer solution. The optimal integer solution of {\bf P} is found for any its optimal solution by solving the linear assignment problem {\bf L}. The existence of polynomial algorithms for problems {\bf P} and {\bf L} proves the polynomial solvability of ${ NP}$-complete problems.
ISBN	-
Item Type	Article
File Type	pdf
File Size	29.34 KB
Language	English
Subjects	-
Unlimited	MYR 0.01
Total read	-
URL	http://arxiv.org/abs/1409.0375

Citation

Review the full bibliography data and make any necessary corrections before using. Always consult your library resources for the exact formatting and punctuation guidelines.

AMA 11th EditionReferences

Panyukov, Anatoly. Polynomial solvability of $NP$-complete problems. Australian National University. September 06, 2023. Accessed November 13, 2024. https://online.provdatabase.com/cite/23468

APA 7th EditionReferences

Panyukov, Anatoly. (2023). Polynomial solvability of $NP$-complete problems. Australian National University. https://online.provdatabase.com/cite/23468

Chicago 17th EditionReferences

Panyukov, Anatoly. Polynomial solvability of $NP$-complete problems. Australian National University. 2023. https://online.provdatabase.com/cite/23468

HarvardReferences

Panyukov, Anatoly. (2023). Polynomial solvability of $NP$-complete problems. [Online]. Australian National University. Available from: https://online.provdatabase.com/cite/23468. (Accessed 13 November 2024).

Harvard AustraliaReferences

Panyukov, Anatoly, 2023, Polynomial solvability of $NP$-complete problems, Australian National University, viewed 13 November 2024, <https://online.provdatabase.com/cite/23468>

MLA 9th EditionWorks Cited

Panyukov, Anatoly. Polynomial solvability of $NP$-complete problems. Australian National University, 2023. PROV Database, https://online.provdatabase.com/cite/23468.

Share this eBook