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.
Property | Value |
---|---|
dbo:abstract |
|
dbo:wikiPageID |
|
dbo:wikiPageLength |
|
dbo:wikiPageRevisionID |
|
dbo:wikiPageWikiLink |
|
dbp:wikiPageUsesTemplate | |
dct:subject | |
rdfs:comment |
|
rdfs:label |
|
owl:sameAs | |
prov:wasDerivedFrom | |
foaf:isPrimaryTopicOf | |
is dbo:wikiPageWikiLink of | |
is foaf:primaryTopic of |