2676:
275:
139:
96:
1222:
874:
82:
To solve the deterministic rendezvous problem, both robots must be given a sequence of deterministic instructions which allow the robots to use their known information to find each other. The robots are considered to have found each other if they are both occupying the same node in the graph during
1796:
863:
steps where the robot rests. The universal traversal sequence for the size of the actual graph will be run by one robot while the other rests for the number of steps in that traversal. However, this only works if the two robots are activated at the same time.
2333:
2662:
2503:
2175:
845:
664:
1523:
366:, where the robots must keep track of each edge that they have traversed. This is a drawback because it places assumptions on the structure of the graph (namely, how it is labeled), and the robots' sensory and memory capabilities.
1515:
455:
is the maximum degree of the graph. Any instructions in the chosen universal traversal sequence which specify that the robot travels to a neighbor of the current node which doesn't exist (i.e., the current node has degree <
1400:
1217:{\displaystyle \sigma _{1}0^{u_{1}-1}\sigma _{2}0^{u_{1}-1}\sigma _{3}0^{u_{1}-1}...\sigma _{u_{1}}0^{u_{1}-1}0^{2u_{1}}\pi _{1}0^{u_{2}-1}\pi _{2}0^{u_{2}-1}\pi _{3}0^{u_{2}-1}...\pi _{u_{2}}0^{u_{2}-1}0^{2u_{2}}}
2012:
233:
1889:
2179:
2508:
2349:
2028:
669:
485:
356:
422:
1307:
2910:
471:
The basic idea of Ta-Shma and Zwick's solution is that if one of the robots completes a complete traversal of the graph while the other robot remains idle, or
475:, then the two robots are guaranteed to meet. Since the size of the graph is unknown, the robots run universal traversal sequences for increasing values of
1406:
2869:
Aleliunas, R.; Karp, R.; Lipton, R.; Lovรกsz, L.; Rackoff, C. (1979). "Random walks, universal traversal sequences, and the complexity of maze problems".
1791:{\displaystyle D_{u_{1}-1}((U_{1}U_{1})^{L{\bar {L}}})D_{u_{2}-1}((U_{2}U_{2})^{L{\bar {L}}})...D_{u_{2^{k}}-1}((U_{2^{k}}U_{2^{k}})^{L{\bar {L}}})...}
1313:
443:
with a set number of vertices and for any starting vertex. Since the robots may not be in a regular graph, a universal traversal sequence for
2339:. One chunk consists of a universal traversal sequence with interleaved rest periods, while the other chunk is a rest period of length 2
32:
sequence of instructions. Although each robot follows the same instruction sequence, a unique label assigned to each robot is used for
1898:
867:
To cover the case where the robots are activated at different times, the sequence to run will include rest periods of length u
172:
36:. Typically, the robots act synchronously, though non-synchronous versions of the deterministic rendezvous problem exist.
1803:
169:
In 2006, Dessmark et al. presented a solution which solves the deterministic rendezvous problem in time proportional to
49:
1520:
Assuming that one robot's label is 0 and that the other robot's label is 1, the sequence that each robot would run is:
479:, while periodically resting. Whether a robot rests before or after a traversal depends upon the value of its label.
126:
A number of algorithms exist to solve the deterministic rendezvous problem. Some of the solutions are listed below:
2905:
44:
In the synchronous version of the deterministic rendezvous problem, both robots are initially placed at arbitrary
871:
after each step (in the traversal and the rest period). For example, one of the robots would run the sequence:
1251:
In order to formally present the sequence that each robot will run, some additional notation is needed. Let:
308:
2328:{\displaystyle (\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1})^{\bar {L}}}
2762:(April 2014). "Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences".
2717:) time steps and how to deal with arbitrary labels (which increases the time until the robots meet to O(
2657:{\displaystyle \sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}0^{2m^{2}}}
2498:{\displaystyle 0^{2m^{2}}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}}
69:
45:
381:
262:
is an input parameter of the deterministic rendezvous problem and can therefore be arbitrarily large.
2706:
The sequence of instructions listed above will allow two robots with labels 0 and 1 to meet after O(
2170:{\displaystyle (\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1})^{L}}
1271:
840:{\displaystyle 0^{u_{1}}U_{1}0^{u_{2}}U_{2}0^{u_{4}}U_{4}0^{u_{8}}U_{8}...0^{u_{2^{i}}}U_{2^{i}}...}
659:{\displaystyle U_{1}0^{u_{1}}U_{2}0^{u_{2}}U_{4}0^{u_{4}}U_{8}0^{u_{8}}...U_{2^{i}}0^{u_{2^{i}}}...}
468:, effectively allowing the graph to be treated as regular for the purpose of universal traversals.
2882:
2818:
2779:
21:
2798:
33:
2874:
2849:
2810:
2771:
2713:
Ta-Shma and Zwick show how to extend this solution to allow the robots to meet after only O(
436:
429:
358:
time. This is a significant improvement, since this time complexity is not dependent on
2675:
274:
138:
95:
2899:
440:
2886:
2822:
2783:
1510:{\displaystyle D_{k}(\sigma _{1}...\sigma _{m})=\sigma _{1}0^{k}...\sigma _{m}0^{k}}
305:
In 2008, Kowalski and
Malinowski presented a solution which solves the problem in
29:
428:), this solution also doesn't use backtracking. Instead, it uses the notion of
2854:
2837:
2814:
859:
is the number of steps in that universal traversal sequence, and 0 represents
2759:
375:
460:) are ignored. By doing this, all nodes in the graph with degree less than
464:
are treated as having enough self-loops to bring their total degree up to
435:
A universal traversal sequence is a sequence of instructions comprising a
2878:
1395:{\displaystyle \sigma ^{m_{1}..m_{k}}=\sigma _{1}^{m}...\sigma _{k}^{m}}
424:
time. In addition to the reduced time complexity (which doesn't rely on
2871:
20th Annual
Symposium on Foundations of Computer Science (SFCS 1979)
2775:
78:, the label of the robot (typically taking the form of a bit string)
2007:{\textstyle D_{u_{i}-1}((U_{i}U_{i})^{L}(U_{i}U_{i})^{\bar {L}})}
2346:
If the robot's label is 0, then each block it runs is equal to:
362:. This solution has one major drawback, though. It makes use of
52:. The size and structure of the graph is unknown to the robots.
2670:
269:
133:
90:
2797:
Dessmark, A.; Fraingnaud, P.; Kowalski, D.; Pelc, A. (2006).
248:
is the difference in activation time between the two robots
2505:
If the label is 1, then each block it runs is equal to:
254:
is the length of the shorter of the labels of the robots
228:{\textstyle O\left(n^{5}{\sqrt {\tau l}}+n^{10}l\right)}
2687:
482:
For example, one of the robots could run the sequence:
286:
150:
107:
1901:
1806:
384:
311:
175:
62:, the number of time steps since it has been activated
2511:
2352:
2182:
2031:
1526:
1409:
1316:
1274:
877:
672:
488:
1884:{\textstyle D_{u_{i}-1}((U_{i}U_{i})^{L{\bar {L}}})}
851:is a universal traversal sequence for a graph with
2656:
2497:
2327:
2169:
2006:
1883:
1790:
1509:
1394:
1301:
1216:
839:
658:
416:
350:
227:
55:The information known by a robot is as follows:
2753:
2751:
2749:
2747:
2745:
2743:
2741:
2739:
2737:
8:
72:of the node currently occupied by the robot
2025:, the block can be further simplified to:
2853:
2646:
2638:
2622:
2612:
2587:
2577:
2561:
2551:
2526:
2516:
2510:
2483:
2473:
2448:
2438:
2422:
2412:
2387:
2377:
2365:
2357:
2351:
2313:
2312:
2296:
2286:
2261:
2251:
2235:
2225:
2200:
2190:
2181:
2161:
2145:
2135:
2110:
2100:
2084:
2074:
2049:
2039:
2030:
1989:
1988:
1978:
1968:
1955:
1945:
1935:
1911:
1906:
1900:
1865:
1864:
1860:
1850:
1840:
1816:
1811:
1805:
1763:
1762:
1758:
1746:
1741:
1729:
1724:
1698:
1693:
1688:
1659:
1658:
1654:
1644:
1634:
1610:
1605:
1585:
1584:
1580:
1570:
1560:
1536:
1531:
1525:
1501:
1491:
1472:
1462:
1446:
1427:
1414:
1408:
1386:
1381:
1362:
1357:
1342:
1326:
1321:
1315:
1276:
1275:
1273:
1206:
1198:
1180:
1175:
1163:
1158:
1131:
1126:
1116:
1098:
1093:
1083:
1065:
1060:
1050:
1038:
1030:
1012:
1007:
995:
990:
963:
958:
948:
930:
925:
915:
897:
892:
882:
876:
820:
815:
801:
796:
791:
775:
763:
758:
748:
736:
731:
721:
709:
704:
694:
682:
677:
671:
666:while the other robot runs the sequence:
637:
632:
627:
615:
610:
589:
584:
574:
562:
557:
547:
535:
530:
520:
508:
503:
493:
487:
397:
383:
337:
324:
310:
211:
194:
188:
174:
2733:
351:{\textstyle O\left(n^{15}+l^{3}\right)}
2911:Computational problems in graph theory
374:The solution presented by Ta-Shma and
28:, must find each other by following a
2836:Kowalski, D.; Malinowski, A. (2008).
2335:Both of the above lines are known as
7:
2799:"Deterministic rendezvous in graphs"
242:is the number of nodes in the graph
48:in a finite, connected, undirected
2838:"How to meet in anonymous network"
417:{\textstyle O\left(n^{5}+l\right)}
258:This solution is not ideal, since
14:
2674:
273:
137:
94:
18:deterministic rendezvous problem
2764:ACM Transactions on Algorithms
2318:
2309:
2183:
2158:
2032:
2001:
1994:
1985:
1961:
1952:
1928:
1925:
1878:
1870:
1857:
1833:
1830:
1776:
1768:
1755:
1717:
1714:
1672:
1664:
1651:
1627:
1624:
1598:
1590:
1577:
1553:
1550:
1452:
1420:
1302:{\displaystyle {\bar {L}}=1-L}
1281:
378:in 2014 solves the problem in
1:
430:universal traversal sequences
2842:Theoretical Computer Science
432:to help solve the problem.
2927:
2855:10.1016/j.tcs.2008.02.010
2815:10.1007/s00453-006-0074-2
1895:and can be rewritten as
266:Kowalski and Malinowski
2658:
2499:
2329:
2171:
2008:
1885:
1792:
1511:
1396:
1303:
1218:
841:
660:
418:
352:
229:
24:where the players, or
2659:
2500:
2330:
2172:
2009:
1886:
1793:
1512:
1397:
1304:
1219:
842:
661:
419:
353:
230:
2879:10.1109/SFCS.1979.34
2509:
2350:
2180:
2029:
1899:
1804:
1524:
1407:
1314:
1272:
875:
670:
486:
382:
309:
173:
83:the same time step.
20:is a variant of the
1391:
1367:
2686:. You can help by
2654:
2495:
2325:
2167:
2004:
1881:
1788:
1507:
1392:
1377:
1353:
1299:
1214:
837:
656:
414:
348:
285:. You can help by
225:
149:. You can help by
106:. You can help by
22:rendezvous problem
2906:Cooperative games
2704:
2703:
2321:
1997:
1873:
1800:The sub-sequence
1771:
1667:
1593:
1284:
447:nodes and degree
370:Ta-Shma and Zwick
303:
302:
202:
167:
166:
124:
123:
34:symmetry breaking
2918:
2891:
2890:
2866:
2860:
2859:
2857:
2848:(1โ2): 144โ156.
2833:
2827:
2826:
2794:
2788:
2787:
2758:Ta-Shma, Amnon;
2755:
2699:
2696:
2678:
2671:
2663:
2661:
2660:
2655:
2653:
2652:
2651:
2650:
2633:
2632:
2617:
2616:
2598:
2597:
2582:
2581:
2572:
2571:
2556:
2555:
2537:
2536:
2521:
2520:
2504:
2502:
2501:
2496:
2494:
2493:
2478:
2477:
2459:
2458:
2443:
2442:
2433:
2432:
2417:
2416:
2398:
2397:
2382:
2381:
2372:
2371:
2370:
2369:
2334:
2332:
2331:
2326:
2324:
2323:
2322:
2314:
2307:
2306:
2291:
2290:
2272:
2271:
2256:
2255:
2246:
2245:
2230:
2229:
2211:
2210:
2195:
2194:
2176:
2174:
2173:
2168:
2166:
2165:
2156:
2155:
2140:
2139:
2121:
2120:
2105:
2104:
2095:
2094:
2079:
2078:
2060:
2059:
2044:
2043:
2013:
2011:
2010:
2005:
2000:
1999:
1998:
1990:
1983:
1982:
1973:
1972:
1960:
1959:
1950:
1949:
1940:
1939:
1924:
1923:
1916:
1915:
1890:
1888:
1887:
1882:
1877:
1876:
1875:
1874:
1866:
1855:
1854:
1845:
1844:
1829:
1828:
1821:
1820:
1797:
1795:
1794:
1789:
1775:
1774:
1773:
1772:
1764:
1753:
1752:
1751:
1750:
1736:
1735:
1734:
1733:
1713:
1712:
1705:
1704:
1703:
1702:
1671:
1670:
1669:
1668:
1660:
1649:
1648:
1639:
1638:
1623:
1622:
1615:
1614:
1597:
1596:
1595:
1594:
1586:
1575:
1574:
1565:
1564:
1549:
1548:
1541:
1540:
1516:
1514:
1513:
1508:
1506:
1505:
1496:
1495:
1477:
1476:
1467:
1466:
1451:
1450:
1432:
1431:
1419:
1418:
1401:
1399:
1398:
1393:
1390:
1385:
1366:
1361:
1349:
1348:
1347:
1346:
1331:
1330:
1308:
1306:
1305:
1300:
1286:
1285:
1277:
1223:
1221:
1220:
1215:
1213:
1212:
1211:
1210:
1193:
1192:
1185:
1184:
1170:
1169:
1168:
1167:
1144:
1143:
1136:
1135:
1121:
1120:
1111:
1110:
1103:
1102:
1088:
1087:
1078:
1077:
1070:
1069:
1055:
1054:
1045:
1044:
1043:
1042:
1025:
1024:
1017:
1016:
1002:
1001:
1000:
999:
976:
975:
968:
967:
953:
952:
943:
942:
935:
934:
920:
919:
910:
909:
902:
901:
887:
886:
846:
844:
843:
838:
827:
826:
825:
824:
810:
809:
808:
807:
806:
805:
780:
779:
770:
769:
768:
767:
753:
752:
743:
742:
741:
740:
726:
725:
716:
715:
714:
713:
699:
698:
689:
688:
687:
686:
665:
663:
662:
657:
646:
645:
644:
643:
642:
641:
622:
621:
620:
619:
596:
595:
594:
593:
579:
578:
569:
568:
567:
566:
552:
551:
542:
541:
540:
539:
525:
524:
515:
514:
513:
512:
498:
497:
423:
421:
420:
415:
413:
409:
402:
401:
357:
355:
354:
349:
347:
343:
342:
341:
329:
328:
298:
295:
277:
270:
234:
232:
231:
226:
224:
220:
216:
215:
203:
195:
193:
192:
162:
159:
141:
134:
119:
116:
98:
91:
2926:
2925:
2921:
2920:
2919:
2917:
2916:
2915:
2896:
2895:
2894:
2868:
2867:
2863:
2835:
2834:
2830:
2796:
2795:
2791:
2776:10.1145/2601068
2757:
2756:
2735:
2731:
2725:) time steps).
2700:
2694:
2691:
2684:needs expansion
2669:
2642:
2634:
2618:
2608:
2583:
2573:
2557:
2547:
2522:
2512:
2507:
2506:
2479:
2469:
2444:
2434:
2418:
2408:
2383:
2373:
2361:
2353:
2348:
2347:
2308:
2292:
2282:
2257:
2247:
2231:
2221:
2196:
2186:
2178:
2177:
2157:
2141:
2131:
2106:
2096:
2080:
2070:
2045:
2035:
2027:
2026:
2024:
2020:
1984:
1974:
1964:
1951:
1941:
1931:
1907:
1902:
1897:
1896:
1856:
1846:
1836:
1812:
1807:
1802:
1801:
1754:
1742:
1737:
1725:
1720:
1694:
1689:
1684:
1650:
1640:
1630:
1606:
1601:
1576:
1566:
1556:
1532:
1527:
1522:
1521:
1497:
1487:
1468:
1458:
1442:
1423:
1410:
1405:
1404:
1338:
1322:
1317:
1312:
1311:
1270:
1269:
1247:
1239:
1235:
1227:
1202:
1194:
1176:
1171:
1159:
1154:
1127:
1122:
1112:
1094:
1089:
1079:
1061:
1056:
1046:
1034:
1026:
1008:
1003:
991:
986:
959:
954:
944:
926:
921:
911:
893:
888:
878:
873:
872:
870:
858:
850:
816:
811:
797:
792:
787:
771:
759:
754:
744:
732:
727:
717:
705:
700:
690:
678:
673:
668:
667:
633:
628:
623:
611:
606:
585:
580:
570:
558:
553:
543:
531:
526:
516:
504:
499:
489:
484:
483:
451:is used, where
437:graph traversal
393:
392:
388:
380:
379:
372:
333:
320:
319:
315:
307:
306:
299:
293:
290:
283:needs expansion
268:
207:
184:
183:
179:
171:
170:
163:
157:
154:
147:needs expansion
132:
130:Dessmark et al.
120:
114:
111:
104:needs expansion
89:
42:
12:
11:
5:
2924:
2922:
2914:
2913:
2908:
2898:
2897:
2893:
2892:
2861:
2828:
2789:
2732:
2730:
2727:
2710:) time steps.
2702:
2701:
2681:
2679:
2668:
2665:
2649:
2645:
2641:
2637:
2631:
2628:
2625:
2621:
2615:
2611:
2607:
2604:
2601:
2596:
2593:
2590:
2586:
2580:
2576:
2570:
2567:
2564:
2560:
2554:
2550:
2546:
2543:
2540:
2535:
2532:
2529:
2525:
2519:
2515:
2492:
2489:
2486:
2482:
2476:
2472:
2468:
2465:
2462:
2457:
2454:
2451:
2447:
2441:
2437:
2431:
2428:
2425:
2421:
2415:
2411:
2407:
2404:
2401:
2396:
2393:
2390:
2386:
2380:
2376:
2368:
2364:
2360:
2356:
2320:
2317:
2311:
2305:
2302:
2299:
2295:
2289:
2285:
2281:
2278:
2275:
2270:
2267:
2264:
2260:
2254:
2250:
2244:
2241:
2238:
2234:
2228:
2224:
2220:
2217:
2214:
2209:
2206:
2203:
2199:
2193:
2189:
2185:
2164:
2160:
2154:
2151:
2148:
2144:
2138:
2134:
2130:
2127:
2124:
2119:
2116:
2113:
2109:
2103:
2099:
2093:
2090:
2087:
2083:
2077:
2073:
2069:
2066:
2063:
2058:
2055:
2052:
2048:
2042:
2038:
2034:
2022:
2018:
2003:
1996:
1993:
1987:
1981:
1977:
1971:
1967:
1963:
1958:
1954:
1948:
1944:
1938:
1934:
1930:
1927:
1922:
1919:
1914:
1910:
1905:
1891:is known as a
1880:
1872:
1869:
1863:
1859:
1853:
1849:
1843:
1839:
1835:
1832:
1827:
1824:
1819:
1815:
1810:
1787:
1784:
1781:
1778:
1770:
1767:
1761:
1757:
1749:
1745:
1740:
1732:
1728:
1723:
1719:
1716:
1711:
1708:
1701:
1697:
1692:
1687:
1683:
1680:
1677:
1674:
1666:
1663:
1657:
1653:
1647:
1643:
1637:
1633:
1629:
1626:
1621:
1618:
1613:
1609:
1604:
1600:
1592:
1589:
1583:
1579:
1573:
1569:
1563:
1559:
1555:
1552:
1547:
1544:
1539:
1535:
1530:
1518:
1517:
1504:
1500:
1494:
1490:
1486:
1483:
1480:
1475:
1471:
1465:
1461:
1457:
1454:
1449:
1445:
1441:
1438:
1435:
1430:
1426:
1422:
1417:
1413:
1402:
1389:
1384:
1380:
1376:
1373:
1370:
1365:
1360:
1356:
1352:
1345:
1341:
1337:
1334:
1329:
1325:
1320:
1309:
1298:
1295:
1292:
1289:
1283:
1280:
1267:
1260:
1245:
1237:
1233:
1225:
1209:
1205:
1201:
1197:
1191:
1188:
1183:
1179:
1174:
1166:
1162:
1157:
1153:
1150:
1147:
1142:
1139:
1134:
1130:
1125:
1119:
1115:
1109:
1106:
1101:
1097:
1092:
1086:
1082:
1076:
1073:
1068:
1064:
1059:
1053:
1049:
1041:
1037:
1033:
1029:
1023:
1020:
1015:
1011:
1006:
998:
994:
989:
985:
982:
979:
974:
971:
966:
962:
957:
951:
947:
941:
938:
933:
929:
924:
918:
914:
908:
905:
900:
896:
891:
885:
881:
868:
856:
848:
836:
833:
830:
823:
819:
814:
804:
800:
795:
790:
786:
783:
778:
774:
766:
762:
757:
751:
747:
739:
735:
730:
724:
720:
712:
708:
703:
697:
693:
685:
681:
676:
655:
652:
649:
640:
636:
631:
626:
618:
614:
609:
605:
602:
599:
592:
588:
583:
577:
573:
565:
561:
556:
550:
546:
538:
534:
529:
523:
519:
511:
507:
502:
496:
492:
412:
408:
405:
400:
396:
391:
387:
371:
368:
346:
340:
336:
332:
327:
323:
318:
314:
301:
300:
280:
278:
267:
264:
256:
255:
249:
243:
223:
219:
214:
210:
206:
201:
198:
191:
187:
182:
178:
165:
164:
144:
142:
131:
128:
122:
121:
101:
99:
88:
85:
80:
79:
73:
63:
41:
38:
13:
10:
9:
6:
4:
3:
2:
2923:
2912:
2909:
2907:
2904:
2903:
2901:
2888:
2884:
2880:
2876:
2872:
2865:
2862:
2856:
2851:
2847:
2843:
2839:
2832:
2829:
2824:
2820:
2816:
2812:
2808:
2804:
2800:
2793:
2790:
2785:
2781:
2777:
2773:
2769:
2765:
2761:
2754:
2752:
2750:
2748:
2746:
2744:
2742:
2740:
2738:
2734:
2728:
2726:
2724:
2720:
2716:
2711:
2709:
2698:
2695:December 2016
2689:
2685:
2682:This section
2680:
2677:
2673:
2672:
2666:
2664:
2647:
2643:
2639:
2635:
2629:
2626:
2623:
2619:
2613:
2609:
2605:
2602:
2599:
2594:
2591:
2588:
2584:
2578:
2574:
2568:
2565:
2562:
2558:
2552:
2548:
2544:
2541:
2538:
2533:
2530:
2527:
2523:
2517:
2513:
2490:
2487:
2484:
2480:
2474:
2470:
2466:
2463:
2460:
2455:
2452:
2449:
2445:
2439:
2435:
2429:
2426:
2423:
2419:
2413:
2409:
2405:
2402:
2399:
2394:
2391:
2388:
2384:
2378:
2374:
2366:
2362:
2358:
2354:
2344:
2342:
2338:
2315:
2303:
2300:
2297:
2293:
2287:
2283:
2279:
2276:
2273:
2268:
2265:
2262:
2258:
2252:
2248:
2242:
2239:
2236:
2232:
2226:
2222:
2218:
2215:
2212:
2207:
2204:
2201:
2197:
2191:
2187:
2162:
2152:
2149:
2146:
2142:
2136:
2132:
2128:
2125:
2122:
2117:
2114:
2111:
2107:
2101:
2097:
2091:
2088:
2085:
2081:
2075:
2071:
2067:
2064:
2061:
2056:
2053:
2050:
2046:
2040:
2036:
2015:
1991:
1979:
1975:
1969:
1965:
1956:
1946:
1942:
1936:
1932:
1920:
1917:
1912:
1908:
1903:
1894:
1867:
1861:
1851:
1847:
1841:
1837:
1825:
1822:
1817:
1813:
1808:
1798:
1785:
1782:
1779:
1765:
1759:
1747:
1743:
1738:
1730:
1726:
1721:
1709:
1706:
1699:
1695:
1690:
1685:
1681:
1678:
1675:
1661:
1655:
1645:
1641:
1635:
1631:
1619:
1616:
1611:
1607:
1602:
1587:
1581:
1571:
1567:
1561:
1557:
1545:
1542:
1537:
1533:
1528:
1502:
1498:
1492:
1488:
1484:
1481:
1478:
1473:
1469:
1463:
1459:
1455:
1447:
1443:
1439:
1436:
1433:
1428:
1424:
1415:
1411:
1403:
1387:
1382:
1378:
1374:
1371:
1368:
1363:
1358:
1354:
1350:
1343:
1339:
1335:
1332:
1327:
1323:
1318:
1310:
1296:
1293:
1290:
1287:
1278:
1268:
1265:
1261:
1258:
1254:
1253:
1252:
1249:
1243:
1231:
1207:
1203:
1199:
1195:
1189:
1186:
1181:
1177:
1172:
1164:
1160:
1155:
1151:
1148:
1145:
1140:
1137:
1132:
1128:
1123:
1117:
1113:
1107:
1104:
1099:
1095:
1090:
1084:
1080:
1074:
1071:
1066:
1062:
1057:
1051:
1047:
1039:
1035:
1031:
1027:
1021:
1018:
1013:
1009:
1004:
996:
992:
987:
983:
980:
977:
972:
969:
964:
960:
955:
949:
945:
939:
936:
931:
927:
922:
916:
912:
906:
903:
898:
894:
889:
883:
879:
865:
862:
854:
834:
831:
828:
821:
817:
812:
802:
798:
793:
788:
784:
781:
776:
772:
764:
760:
755:
749:
745:
737:
733:
728:
722:
718:
710:
706:
701:
695:
691:
683:
679:
674:
653:
650:
647:
638:
634:
629:
624:
616:
612:
607:
603:
600:
597:
590:
586:
581:
575:
571:
563:
559:
554:
548:
544:
536:
532:
527:
521:
517:
509:
505:
500:
494:
490:
480:
478:
474:
469:
467:
463:
459:
454:
450:
446:
442:
441:regular graph
438:
433:
431:
427:
410:
406:
403:
398:
394:
389:
385:
377:
369:
367:
365:
361:
344:
338:
334:
330:
325:
321:
316:
312:
297:
294:December 2016
288:
284:
281:This section
279:
276:
272:
271:
265:
263:
261:
253:
250:
247:
244:
241:
238:
237:
236:
221:
217:
212:
208:
204:
199:
196:
189:
185:
180:
176:
161:
158:December 2016
152:
148:
145:This section
143:
140:
136:
135:
129:
127:
118:
115:December 2016
109:
105:
102:This section
100:
97:
93:
92:
86:
84:
77:
74:
71:
67:
64:
61:
58:
57:
56:
53:
51:
47:
39:
37:
35:
31:
30:deterministic
27:
23:
19:
2870:
2864:
2845:
2841:
2831:
2809:(1): 69โ96.
2806:
2803:Algorithmica
2802:
2792:
2767:
2763:
2722:
2718:
2714:
2712:
2707:
2705:
2692:
2688:adding to it
2683:
2345:
2340:
2336:
2016:
1892:
1799:
1519:
1263:
1256:
1250:
1241:
1229:
866:
860:
852:
481:
476:
472:
470:
465:
461:
457:
452:
448:
444:
434:
425:
373:
364:backtracking
363:
359:
304:
291:
287:adding to it
282:
259:
257:
251:
245:
239:
168:
155:
151:adding to it
146:
125:
112:
108:adding to it
103:
81:
75:
65:
59:
54:
43:
25:
17:
15:
2873:: 218โ223.
2900:Categories
2760:Zwick, Uri
2729:References
2770:(3). 12.
2627:−
2610:σ
2592:−
2575:σ
2566:−
2549:σ
2531:−
2514:σ
2488:−
2471:σ
2453:−
2436:σ
2427:−
2410:σ
2392:−
2375:σ
2319:¯
2301:−
2284:σ
2266:−
2249:σ
2240:−
2223:σ
2205:−
2188:σ
2150:−
2133:σ
2115:−
2098:σ
2089:−
2072:σ
2054:−
2037:σ
2021:and m = u
1995:¯
1918:−
1871:¯
1823:−
1769:¯
1707:−
1665:¯
1617:−
1591:¯
1543:−
1489:σ
1460:σ
1444:σ
1425:σ
1379:σ
1355:σ
1319:σ
1294:−
1282:¯
1262:ฯ = ฯ if
1255:ฯ = 0 if
1244:step of U
1232:step of U
1187:−
1156:π
1138:−
1114:π
1105:−
1081:π
1072:−
1048:π
1019:−
988:σ
970:−
946:σ
937:−
913:σ
904:−
880:σ
235:, where:
197:τ
87:Solutions
2887:18719861
2823:22236305
2784:10718957
2667:Analysis
2017:If ฯ = U
855:nodes, u
439:for any
40:Overview
1240:is the
1228:is the
1224:where ฯ
847:where U
2885:
2821:
2782:
2337:chunks
70:degree
68:, the
26:robots
2883:S2CID
2819:S2CID
2780:S2CID
1893:block
1236:and ฯ
473:rests
376:Zwick
50:graph
46:nodes
16:The
2875:doi
2850:doi
2846:399
2811:doi
2772:doi
2690:.
1266:= 1
1259:= 0
289:.
153:.
110:.
2902::
2881:.
2844:.
2840:.
2817:.
2807:46
2805:.
2801:.
2778:.
2768:10
2766:.
2736:^
2343:.
2014:.
1248:.
789:.0
326:15
213:10
2889:.
2877::
2858:.
2852::
2825:.
2813::
2786:.
2774::
2723:l
2721:+
2719:n
2715:n
2708:n
2697:)
2693:(
2648:2
2644:m
2640:2
2636:0
2630:1
2624:m
2620:0
2614:m
2606:.
2603:.
2600:.
2595:1
2589:m
2585:0
2579:1
2569:1
2563:m
2559:0
2553:m
2545:.
2542:.
2539:.
2534:1
2528:m
2524:0
2518:1
2491:1
2485:m
2481:0
2475:m
2467:.
2464:.
2461:.
2456:1
2450:m
2446:0
2440:1
2430:1
2424:m
2420:0
2414:m
2406:.
2403:.
2400:.
2395:1
2389:m
2385:0
2379:1
2367:2
2363:m
2359:2
2355:0
2341:m
2316:L
2310:)
2304:1
2298:m
2294:0
2288:m
2280:.
2277:.
2274:.
2269:1
2263:m
2259:0
2253:1
2243:1
2237:m
2233:0
2227:m
2219:.
2216:.
2213:.
2208:1
2202:m
2198:0
2192:1
2184:(
2163:L
2159:)
2153:1
2147:m
2143:0
2137:m
2129:.
2126:.
2123:.
2118:1
2112:m
2108:0
2102:1
2092:1
2086:m
2082:0
2076:m
2068:.
2065:.
2062:.
2057:1
2051:m
2047:0
2041:1
2033:(
2023:i
2019:i
2002:)
1992:L
1986:)
1980:i
1976:U
1970:i
1966:U
1962:(
1957:L
1953:)
1947:i
1943:U
1937:i
1933:U
1929:(
1926:(
1921:1
1913:i
1909:u
1904:D
1879:)
1868:L
1862:L
1858:)
1852:i
1848:U
1842:i
1838:U
1834:(
1831:(
1826:1
1818:i
1814:u
1809:D
1786:.
1783:.
1780:.
1777:)
1766:L
1760:L
1756:)
1748:k
1744:2
1739:U
1731:k
1727:2
1722:U
1718:(
1715:(
1710:1
1700:k
1696:2
1691:u
1686:D
1682:.
1679:.
1676:.
1673:)
1662:L
1656:L
1652:)
1646:2
1642:U
1636:2
1632:U
1628:(
1625:(
1620:1
1612:2
1608:u
1603:D
1599:)
1588:L
1582:L
1578:)
1572:1
1568:U
1562:1
1558:U
1554:(
1551:(
1546:1
1538:1
1534:u
1529:D
1503:k
1499:0
1493:m
1485:.
1482:.
1479:.
1474:k
1470:0
1464:1
1456:=
1453:)
1448:m
1440:.
1437:.
1434:.
1429:1
1421:(
1416:k
1412:D
1388:m
1383:k
1375:.
1372:.
1369:.
1364:m
1359:1
1351:=
1344:k
1340:m
1336:.
1333:.
1328:1
1324:m
1297:L
1291:1
1288:=
1279:L
1264:b
1257:b
1246:2
1242:i
1238:i
1234:1
1230:i
1226:i
1208:2
1204:u
1200:2
1196:0
1190:1
1182:2
1178:u
1173:0
1165:2
1161:u
1152:.
1149:.
1146:.
1141:1
1133:2
1129:u
1124:0
1118:3
1108:1
1100:2
1096:u
1091:0
1085:2
1075:1
1067:2
1063:u
1058:0
1052:1
1040:1
1036:u
1032:2
1028:0
1022:1
1014:1
1010:u
1005:0
997:1
993:u
984:.
981:.
978:.
973:1
965:1
961:u
956:0
950:3
940:1
932:1
928:u
923:0
917:2
907:1
899:1
895:u
890:0
884:1
869:i
861:k
857:i
853:i
849:i
835:.
832:.
829:.
822:i
818:2
813:U
803:i
799:2
794:u
785:.
782:.
777:8
773:U
765:8
761:u
756:0
750:4
746:U
738:4
734:u
729:0
723:2
719:U
711:2
707:u
702:0
696:1
692:U
684:1
680:u
675:0
654:.
651:.
648:.
639:i
635:2
630:u
625:0
617:i
613:2
608:U
604:.
601:.
598:.
591:8
587:u
582:0
576:8
572:U
564:4
560:u
555:0
549:4
545:U
537:2
533:u
528:0
522:2
518:U
510:1
506:u
501:0
495:1
491:U
477:n
466:d
462:d
458:d
453:d
449:d
445:n
426:ฯ
411:)
407:l
404:+
399:5
395:n
390:(
386:O
360:ฯ
345:)
339:3
335:l
331:+
322:n
317:(
313:O
296:)
292:(
260:ฯ
252:l
246:ฯ
240:n
222:)
218:l
209:n
205:+
200:l
190:5
186:n
181:(
177:O
160:)
156:(
117:)
113:(
76:L
66:d
60:T
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
