| http://dbpedia.org/ontology/abstract
|
In computational complexity theory and com … In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens. Given a graph , an initial state of tokens is defined by a subset of the vertices of the graph; let . Moving a token from vertex to vertex is valid if and are joined by a path in that does not contain any other tokens; note that the distance traveled within the graph is inconsequential, and moving a token across multiple edges sequentially is considered a single move. A desired end state is defined as another subset . The goal is to minimize the number of valid moves to reach the end state from the initial state.each the end state from the initial state.
|
| http://dbpedia.org/ontology/wikiPageID
|
44645174
|
| http://dbpedia.org/ontology/wikiPageLength
|
7471
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1032294014
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Reduction_%28complexity%29 +
, http://dbpedia.org/resource/Set_cover +
, http://dbpedia.org/resource/Combinatorics +
, http://dbpedia.org/resource/Approximation_algorithm +
, http://dbpedia.org/resource/L-reduction +
, http://dbpedia.org/resource/APX +
, http://dbpedia.org/resource/Reconfiguration +
, http://dbpedia.org/resource/Sliding_puzzle +
, http://dbpedia.org/resource/Category:Reconfiguration +
, http://dbpedia.org/resource/Category:NP-complete_problems +
, http://dbpedia.org/resource/Category:Computational_problems_in_graph_theory +
, http://dbpedia.org/resource/Category:Approximation_algorithms +
, http://dbpedia.org/resource/Computational_complexity_theory +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Reflist +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Reconfiguration +
, http://dbpedia.org/resource/Category:NP-complete_problems +
, http://dbpedia.org/resource/Category:Computational_problems_in_graph_theory +
, http://dbpedia.org/resource/Category:Approximation_algorithms +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Token_reconfiguration?oldid=1032294014&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Token_reconfiguration +
|
| owl:sameAs |
http://yago-knowledge.org/resource/Token_reconfiguration +
, http://rdf.freebase.com/ns/m.012g4l5h +
, http://www.wikidata.org/entity/Q25303754 +
, https://global.dbpedia.org/id/2NmxW +
, http://dbpedia.org/resource/Token_reconfiguration +
|
| rdfs:comment |
In computational complexity theory and com … In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens. Given a graph , an initial state of tokens is defined by a subset of the vertices of the graph; let . Moving a token from vertex to vertex is valid if and are joined by a path in that does not contain any other tokens; note that the distance traveled within the graph is inconsequential, and moving a token across multiple edges sequentially is considered a single move. A desired end state is defined as another subset . The goal is to minimize the number of valid moves to reach the end state from the initial state.each the end state from the initial state.
|
| rdfs:label |
Token reconfiguration
|
