Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Set_TSP_problem> ?p ?o }
Showing triples 1 to 34 of
34
with 100 triples per page.
- Set_TSP_problem abstract "In combinatorial optimization, the set TSP, also known as the, generalized TSP, group TSP, One-of-a-Set TSP, Multiple Choice TSP or Covering Salesman Problem, is a generalization of the Traveling salesman problem (TSP), whereby it is required to find a shortest tour in a graph which visits all specified disjoint subsets of the vertices of a graph. The ordinary TSP is a special case of the set TSP when all subsets to be visited are singletons. Therefore the set TSP is also NP-hard.There is a direct reduction from set TSP to asymmetric TSP, and thus from set TSP to TSP. The idea is to arbitrarily assign a directed cycle to each set. The salesman, when visiting a vertex in some set, then walks around the cycle for free. To not use the cycle would ultimately be very costly.".
- Set_TSP_problem wikiPageID "21182177".
- Set_TSP_problem wikiPageLength "1350".
- Set_TSP_problem wikiPageOutDegree "9".
- Set_TSP_problem wikiPageRevisionID "657392479".
- Set_TSP_problem wikiPageWikiLink Category:Combinatorial_optimization.
- Set_TSP_problem wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Set_TSP_problem wikiPageWikiLink Category:NP-complete_problems.
- Set_TSP_problem wikiPageWikiLink Category:Operations_research.
- Set_TSP_problem wikiPageWikiLink Category:Travelling_salesman_problem.
- Set_TSP_problem wikiPageWikiLink Combinatorial_optimization.
- Set_TSP_problem wikiPageWikiLink NP-hardness.
- Set_TSP_problem wikiPageWikiLink Singleton_(mathematics).
- Set_TSP_problem wikiPageWikiLink Travelling_salesman_problem.
- Set_TSP_problem wikiPageWikiLinkText "Set TSP problem".
- Set_TSP_problem wikiPageWikiLinkText "generalized travelling salesman problem".
- Set_TSP_problem wikiPageUsesTemplate Template:Reflist.
- Set_TSP_problem subject Category:Combinatorial_optimization.
- Set_TSP_problem subject Category:Computational_problems_in_graph_theory.
- Set_TSP_problem subject Category:NP-complete_problems.
- Set_TSP_problem subject Category:Operations_research.
- Set_TSP_problem subject Category:Travelling_salesman_problem.
- Set_TSP_problem hypernym Generalization.
- Set_TSP_problem type Algorithm.
- Set_TSP_problem type Discipline.
- Set_TSP_problem type Field.
- Set_TSP_problem comment "In combinatorial optimization, the set TSP, also known as the, generalized TSP, group TSP, One-of-a-Set TSP, Multiple Choice TSP or Covering Salesman Problem, is a generalization of the Traveling salesman problem (TSP), whereby it is required to find a shortest tour in a graph which visits all specified disjoint subsets of the vertices of a graph. The ordinary TSP is a special case of the set TSP when all subsets to be visited are singletons.".
- Set_TSP_problem label "Set TSP problem".
- Set_TSP_problem sameAs Q4329453.
- Set_TSP_problem sameAs m.05b_2p8.
- Set_TSP_problem sameAs Обобщённая_задача_коммивояжёра.
- Set_TSP_problem sameAs Q4329453.
- Set_TSP_problem wasDerivedFrom Set_TSP_problem?oldid=657392479.
- Set_TSP_problem isPrimaryTopicOf Set_TSP_problem.