Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
How to Sort by Walking on a Tree
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Consider a graph
G
with
n
vertices. On each vertex we place a box. These
n
vertices and
n
boxes are both numbered from 1 to
n
and initially shuffled according to a permutation
π
∈
S
n
. We introduce a sorting problem for a single robot: In every step, the robot can walk along an edge of
G
and can carry at most one box at a time. At a vertex, it may swap the box placed there with the box it is carrying. How many steps does the robot need to sort all the boxes?
We present an algorithm that produces a shortest possible sorting walk for such a robot if
G
is a tree. The algorithm runs in time
$\mathcal{O}(n^2)$
and can be simplified further if
G
is a path. We show that for planar graphs the problem of finding a shortest possible sorting walk is
$\mathcal{NP}$
-complete.