The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian. The problem is clearly NP-hard in general case (since its solution gives an answer to the NP-complete problem of determining whether a given graph has a Hamiltonian cycle). The associated decision problem of determining whether K edges can be added to a given graph to produce a Hamiltonian graph is NP-complete. Moreover, Hamiltonian completion belongs to the APX complexity class, i.e., it is unlikely that efficient constant ratio approximation algorithms exist for this problem.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Hamiltonian completion (en)
- Гамильтоново дополнение (ru)
- Гамільтонове доповнення (uk)
|
| rdfs:comment
| - The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian. The problem is clearly NP-hard in general case (since its solution gives an answer to the NP-complete problem of determining whether a given graph has a Hamiltonian cycle). The associated decision problem of determining whether K edges can be added to a given graph to produce a Hamiltonian graph is NP-complete. Moreover, Hamiltonian completion belongs to the APX complexity class, i.e., it is unlikely that efficient constant ratio approximation algorithms exist for this problem. (en)
- Задача гамильтонова дополнения — это задача нахождения минимального числа рёбер, которое нужно добавить в граф, чтобы он стал гамильтоновым. Ясно, что задача в общем случае NP-трудна (поскольку её решение даёт ответ на NP-полную задачу определения, имеет ли граф гамильтонов цикл). Связанная задача разрешимости, может ли добавление K рёбер в заданный граф дать гамильтонов граф, является NP-полной. Более того, Ву, Лу и Ли показали, что существование эффективных алгоритмов с постоянным коэффициентом аппроксимации для этой задачи маловероятно. (ru)
- Задача гамільтонового доповнення — це задача знаходження найменшого числа ребер, які потрібно додати в граф, щоб він став гамільтоновим. Ясно, що задача в загальному випадку NP-складна (оскільки її розв'язок дає відповідь на NP-повну задачу визначення, чи має граф гамільтонів цикл). Пов'язана задача розв'язності, чи може додавання K ребер в заданий граф дати гамільтонів граф, є NP-повною. Понад це, Ву, Лу і Лі показали, що існування ефективних алгоритмів зі сталим коефіцієнтом апроксимації для цієї задачі малоймовірне. (uk)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| has abstract
| - The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian. The problem is clearly NP-hard in general case (since its solution gives an answer to the NP-complete problem of determining whether a given graph has a Hamiltonian cycle). The associated decision problem of determining whether K edges can be added to a given graph to produce a Hamiltonian graph is NP-complete. Moreover, Hamiltonian completion belongs to the APX complexity class, i.e., it is unlikely that efficient constant ratio approximation algorithms exist for this problem. The problem may be solved in polynomial time for certain classes of graphs, including series–parallel graphs and their generalizations, which include outerplanar graphs, as well as for a line graph of a treeor a cactus graph. Gamarnik et al. use a linear time algorithm for solving the problem on trees to study the asymptotic number of edges that must be added for sparse random graphs to make them Hamiltonian. (en)
- Задача гамильтонова дополнения — это задача нахождения минимального числа рёбер, которое нужно добавить в граф, чтобы он стал гамильтоновым. Ясно, что задача в общем случае NP-трудна (поскольку её решение даёт ответ на NP-полную задачу определения, имеет ли граф гамильтонов цикл). Связанная задача разрешимости, может ли добавление K рёбер в заданный граф дать гамильтонов граф, является NP-полной. Более того, Ву, Лу и Ли показали, что существование эффективных алгоритмов с постоянным коэффициентом аппроксимации для этой задачи маловероятно. Задача может быть решена полиномиальное время для некоторых классов графов, куда входят параллельно-последовательные графы и их обобщения, которые включают внешнепланарные графы. В эти классы входят также рёберные графы деревьеви кактусы. Гамарник и Свириденко использовали алгоритм линейного времени для решения задачи на деревьях для изучения асимптотического числа рёбер, которые нужно добавить к разреженным случайным графам, чтобы сделать их гамильтоновыми. (ru)
- Задача гамільтонового доповнення — це задача знаходження найменшого числа ребер, які потрібно додати в граф, щоб він став гамільтоновим. Ясно, що задача в загальному випадку NP-складна (оскільки її розв'язок дає відповідь на NP-повну задачу визначення, чи має граф гамільтонів цикл). Пов'язана задача розв'язності, чи може додавання K ребер в заданий граф дати гамільтонів граф, є NP-повною. Понад це, Ву, Лу і Лі показали, що існування ефективних алгоритмів зі сталим коефіцієнтом апроксимації для цієї задачі малоймовірне. Задачу можна розв'язати за поліноміальний час для деяких класів графів, серед яких паралельно-послідовні графи і їх узагальнення, які включають зовніпланарні графи. До цих класів належать також реберні графи дерев і кактуси. Гамарник і Свириденко використовували алгоритм лінійного часу для розв'язання задачі на деревах для вивчення асимптотичного числа ребер, які потрібно додати до розрідженого випадкового графу, щоб зробити його гамільтоновим. (uk)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)