Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Hamiltonian_completion> ?p ?o. }
Showing items 1 to 29 of
29
with 100 items per page.
- Hamiltonian_completion 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.".
- Hamiltonian_completion wikiPageID "9944425".
- Hamiltonian_completion wikiPageRevisionID "527511741".
- Hamiltonian_completion hasPhotoCollection Hamiltonian_completion.
- Hamiltonian_completion subject Category:Hamiltonian_paths_and_cycles.
- Hamiltonian_completion subject Category:NP-complete_problems.
- Hamiltonian_completion type Abstraction100002137.
- Hamiltonian_completion type Act100030358.
- Hamiltonian_completion type Action100037396.
- Hamiltonian_completion type Attribute100024264.
- Hamiltonian_completion type Condition113920835.
- Hamiltonian_completion type Course100038262.
- Hamiltonian_completion type Difficulty114408086.
- Hamiltonian_completion type Event100029378.
- Hamiltonian_completion type HamiltonianPathsAndCycles.
- Hamiltonian_completion type NP-completeProblems.
- Hamiltonian_completion type Problem114410605.
- Hamiltonian_completion type PsychologicalFeature100023100.
- Hamiltonian_completion type State100024720.
- Hamiltonian_completion type Way100415676.
- Hamiltonian_completion type YagoPermanentlyLocatedEntity.
- Hamiltonian_completion 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).".
- Hamiltonian_completion label "Hamiltonian completion".
- Hamiltonian_completion sameAs m.02pxqn7.
- Hamiltonian_completion sameAs Q5645290.
- Hamiltonian_completion sameAs Q5645290.
- Hamiltonian_completion sameAs Hamiltonian_completion.
- Hamiltonian_completion wasDerivedFrom Hamiltonian_completion?oldid=527511741.
- Hamiltonian_completion isPrimaryTopicOf Hamiltonian_completion.