E-viri
Recenzirano
Odprti dostop
-
Graf, Daniel
Algorithmica, 08/2017, Letnik: 78, Številka: 4Journal Article
Consider a graph G with n vertices. On each vertex we place a box. The n vertices and n boxes are each numbered from 1 to n , and initially shuffled according to a permutation π . A single robot is given the task to sort these boxes. In every step, the robot can walk along an edge of the graph 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 efficient algorithms that construct such a shortest sorting walk if G is a path or a tree, and we show that the problem is NP -complete for planar graphs. If we minimize the number of swaps in addition to the number of walking steps, it is NP -complete even if G is a tree.
Avtor
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.