Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Bottleneck_traveling_salesman_problem> ?p ?o }
Showing triples 1 to 36 of
36
with 100 triples per page.
- Bottleneck_traveling_salesman_problem abstract "The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph which minimizes the weight of the most weighty edge of the cycle.The problem is known to be NP-hard. The decision problem version of this, \"for a given length x, is there a Hamiltonian cycle in a graph g with no edge longer than x?\", is NP-complete.In an asymmetric bottleneck TSP, there are cases where the weight from node A to B is different from the weight from B to A (e. g. travel time between two cities with a traffic jam in one direction).Euclidean bottleneck TSP, or planar bottleneck TSP, is the bottleneck TSP with the distance being the ordinary Euclidean distance. The problem still remains NP-hard, however many heuristics work better.If the graph is a metric space then there is an efficient approximation algorithm that finds a Hamiltonian cycle with maximum edge weight being no more than twice the optimum.".
- Bottleneck_traveling_salesman_problem wikiPageID "420524".
- Bottleneck_traveling_salesman_problem wikiPageLength "1886".
- Bottleneck_traveling_salesman_problem wikiPageOutDegree "15".
- Bottleneck_traveling_salesman_problem wikiPageRevisionID "509363651".
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Approximation_algorithm.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Category:Combinatorial_optimization.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Category:Graph_algorithms.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Category:Hamiltonian_paths_and_cycles.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Combinatorial_optimization.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Decision_problem.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Discrete_optimization.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Euclidean_distance.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Glossary_of_graph_theory.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Hamiltonian_path.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Metric_space.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink NP-completeness.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink NP-hardness.
- Bottleneck_traveling_salesman_problem wikiPageWikiLink Travelling_salesman_problem.
- Bottleneck_traveling_salesman_problem wikiPageWikiLinkText "Bottleneck traveling salesman problem".
- Bottleneck_traveling_salesman_problem wikiPageWikiLinkText "bottleneck travelling salesman problem".
- Bottleneck_traveling_salesman_problem wikiPageUsesTemplate Template:Reflist.
- Bottleneck_traveling_salesman_problem subject Category:Combinatorial_optimization.
- Bottleneck_traveling_salesman_problem subject Category:Graph_algorithms.
- Bottleneck_traveling_salesman_problem subject Category:Hamiltonian_paths_and_cycles.
- Bottleneck_traveling_salesman_problem hypernym Problem.
- Bottleneck_traveling_salesman_problem type Disease.
- Bottleneck_traveling_salesman_problem type Algorithm.
- Bottleneck_traveling_salesman_problem type Object.
- Bottleneck_traveling_salesman_problem comment "The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph which minimizes the weight of the most weighty edge of the cycle.The problem is known to be NP-hard.".
- Bottleneck_traveling_salesman_problem label "Bottleneck traveling salesman problem".
- Bottleneck_traveling_salesman_problem sameAs Q4949085.
- Bottleneck_traveling_salesman_problem sameAs m.026d5b.
- Bottleneck_traveling_salesman_problem sameAs Q4949085.
- Bottleneck_traveling_salesman_problem wasDerivedFrom Bottleneck_traveling_salesman_problem?oldid=509363651.
- Bottleneck_traveling_salesman_problem isPrimaryTopicOf Bottleneck_traveling_salesman_problem.