{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T15:22:43Z","timestamp":1751383363786},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,5,25]],"date-time":"2013-05-25T00:00:00Z","timestamp":1369440000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,5]]},"DOI":"10.1007\/s00224-013-9484-x","type":"journal-article","created":{"date-parts":[[2013,5,24]],"date-time":"2013-05-24T01:25:41Z","timestamp":1369358741000},"page":"715-730","source":"Crossref","is-referenced-by-count":1,"title":["The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye"],"prefix":"10.1007","volume":"54","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ritwik","family":"Bose","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rezaul","family":"Chowdhury","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"McCauley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,5,25]]},"reference":[{"issue":"3","key":"9484_CR1","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1002\/nav.10011","volume":"49","author":"S. Alpern","year":"2002","unstructured":"Alpern, S.: Rendezvous search on labeled networks. Nav. Res. Logist. 49(3), 256\u2013274 (2002)","journal-title":"Nav. Res. Logist."},{"issue":"1","key":"9484_CR2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1239\/jap\/1032374243","volume":"36","author":"S. Alpern","year":"1999","unstructured":"Alpern, S., Baston, V., Essegaier, S.: Rendezvous search on a graph. J. Appl. Probab. 36(1), 223\u2013231 (1999)","journal-title":"J. Appl. Probab."},{"issue":"3","key":"9484_CR3","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"E. Arkin","year":"1994","unstructured":"Arkin, E., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3), 197\u2013218 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9484_CR4","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1177\/027836498900800406","volume":"8","author":"R.C. Arkin","year":"1989","unstructured":"Arkin, R.C.: Motor schema\u2014based mobile robot navigation. Int. J. Robot. Res. 8(4), 92\u2013112 (1989)","journal-title":"Int. J. Robot. Res."},{"issue":"6","key":"9484_CR5","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1109\/70.736776","volume":"14","author":"T. Balch","year":"1998","unstructured":"Balch, T., Arkin, R.: Behavior-based formation control for multirobot teams. IEEE Trans. Robot. Autom. 14(6), 926\u2013939 (1998)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"9484_CR6","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1109\/ICMAS.2000.858476","volume-title":"Proc. 4th International Conference on Multi Agent Systems","author":"T. Balch","year":"2000","unstructured":"Balch, T., Hybinette, M.: Behavior-based coordination of large-scale robot formations. In: Proc. 4th International Conference on Multi Agent Systems, pp. 363\u2013364 (2000)"},{"key":"9484_CR7","first-page":"373","volume-title":"Proc. 6th International Symposium on Distributed Autonomous Robotic Systems","author":"M. Batalin","year":"2002","unstructured":"Batalin, M., Sukhatme, G.: Spreading out: a local approach to multi-robot coverage. In: Proc. 6th International Symposium on Distributed Autonomous Robotic Systems, pp. 373\u2013382 (2002)"},{"key":"9484_CR8","first-page":"476","volume-title":"Proc. IEEE International Conference on Robotics and Automation (ICRA)","author":"W. Burgard","year":"2000","unstructured":"Burgard, W., Moors, M., Fox, D., Simmons, R., Thrun, S.: Collaborative multi-robot exploration. In: Proc. IEEE International Conference on Robotics and Automation (ICRA), vol. 1, pp. 476\u2013481 (2000)"},{"key":"9484_CR9","doi-asserted-by":"crossref","first-page":"1181","DOI":"10.1007\/3-540-45061-0_90","volume-title":"Automata, Languages and Programming","author":"M. Cieliebak","year":"2003","unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Automata, Languages and Programming, pp. 1181\u20131196. Springer, Berlin (2003)"},{"key":"9484_CR10","unstructured":"Culberson, J., Schaeffer, J.: Efficiently searching the 15-puzzle. Technical report, Department of Computing Science, University of Alberta (1994)"},{"key":"9484_CR11","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1145\/1835698.1835761","volume-title":"Proc. 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)","author":"S. Das","year":"2010","unstructured":"Das, S., Flocchini, P., Santoro, N., Yamashita, M.: On the computational power of oblivious robots: forming a series of geometric patterns. In: Proc. 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 267\u2013276 (2010)"},{"issue":"1","key":"9484_CR12","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s00453-006-0074-2","volume":"46","author":"A. Dessmark","year":"2006","unstructured":"Dessmark, A., Fraigniaud, P., Kowalski, D.R., Pelc, A.: Deterministic rendezvous in graphs. Algorithmica 46(1), 69\u201396 (2006)","journal-title":"Algorithmica"},{"key":"9484_CR13","first-page":"480","volume-title":"Proc. IEEE Intelligent Vehicles Symposium (IV)","author":"P. Flocchini","year":"2000","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Distributed coordination of a set of autonomous mobile robots. In: Proc. IEEE Intelligent Vehicles Symposium (IV), pp. 480\u2013485 (2000)"},{"issue":"1","key":"9484_CR14","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.tcs.2005.01.001","volume":"337","author":"P. Flocchini","year":"2005","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1), 147\u2013168 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9484_CR15","first-page":"10","volume-title":"Proc. 8th Annual ACM Symposium on Theory of Computing (STOC)","author":"M. Garey","year":"1976","unstructured":"Garey, M., Graham, R., Johnson, D.: Some NP-complete geometric problems. In: Proc. 8th Annual ACM Symposium on Theory of Computing (STOC), pp. 10\u201322 (1976)"},{"issue":"3","key":"9484_CR16","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/j.dam.2003.11.010","volume":"144","author":"V. Gervasi","year":"2004","unstructured":"Gervasi, V., Prencipe, G.: Coordination without communication: the case of the flocking problem. Discrete Appl. Math. 144(3), 324\u2013344 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9484_CR17","first-page":"469","volume":"6","author":"J. Gudmundsson","year":"1999","unstructured":"Gudmundsson, J., Levcopoulos, C.: A fast approximation algorithm for TSP with neighborhoods. Nord. J. Comput. 6(4), 469 (1999)","journal-title":"Nord. J. Comput."},{"issue":"1\u20132","key":"9484_CR18","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"R. Hearn","year":"2005","unstructured":"Hearn, R., Demaine, E.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343(1\u20132), 72\u201396 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9484_CR19","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/3-540-45465-9_35","volume-title":"Proc. 29th International Conference on Automata, Languages and Programming (ICALP)","author":"R.A. Hearn","year":"2002","unstructured":"Hearn, R.A., Demaine, E.D.: The nondeterministic constraint logic model of computation: reductions and applications. In: Proc. 29th International Conference on Automata, Languages and Programming (ICALP), pp.\u00a0401\u2013413 (2002)"},{"key":"9484_CR20","doi-asserted-by":"crossref","DOI":"10.1201\/b10581","volume-title":"Games, Puzzles, and Computation","author":"R.A. Hearn","year":"2009","unstructured":"Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. AK Peters, Wellesley (2009)"},{"issue":"4","key":"9484_CR21","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1177\/027836498400300405","volume":"3","author":"J. Hopcroft","year":"1984","unstructured":"Hopcroft, J., Schwartz, J., Sharir, M.: On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the \u201cwarehouseman\u2019s problem\u201d. Int. J. Robot. Res. 3(4), 76\u201388 (1984)","journal-title":"Int. J. Robot. Res."},{"key":"9484_CR22","volume-title":"Sliding Piece Puzzles","author":"E. Hordern","year":"1986","unstructured":"Hordern, E.: Sliding Piece Puzzles. Oxford University Press, London (1986)"},{"issue":"2","key":"9484_CR23","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1019625207705","volume":"13","author":"A. Howard","year":"2002","unstructured":"Howard, A., Matari\u0107, M., Sukhatme, G.: An incremental self-deployment algorithm for mobile sensor networks. Auton. Robots 13(2), 113\u2013126 (2002)","journal-title":"Auton. Robots"},{"key":"9484_CR24","first-page":"299","volume-title":"Proc. 6th International Symposium on Distributed Autonomous Robotics Systems (DARS)","author":"A. Howard","year":"2002","unstructured":"Howard, A., Matari\u0107, M., Sukhatme, G.: Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem. In: Proc. 6th International Symposium on Distributed Autonomous Robotics Systems (DARS), pp. 299\u2013308 (2002)"},{"key":"9484_CR25","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/978-3-540-45058-0_6","volume-title":"Proc. 5th Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"T. Hsiang","year":"2004","unstructured":"Hsiang, T., Arkin, E., Bender, M., Fekete, S., Mitchell, J.: Algorithms for rapidly dispersing robot swarms in unknown environments. In: Proc. 5th Workshop on Algorithmic Foundations of Robotics (WAFR), pp. 77\u201394. Springer, Berlin (2004)"},{"issue":"3","key":"9484_CR26","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1145\/136035.136037","volume":"24","author":"Y. Hwang","year":"1992","unstructured":"Hwang, Y., Ahuja, N.: Gross motion planning\u2014a survey. ACM Comput. Surv. 24(3), 219\u2013291 (1992)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"9484_CR27","first-page":"97","volume":"34","author":"F. Karlemo","year":"2000","unstructured":"Karlemo, F., \u00d6sterg\u00e5rd, P.: On sliding block puzzles. J. Comb. Math. Comb. Comput. 34(1), 97\u2013107 (2000)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"1","key":"9484_CR28","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.tcs.2008.02.010","volume":"399","author":"D.R. Kowalski","year":"2008","unstructured":"Kowalski, D.R., Malinowski, A.: How to meet in anonymous network. Theor. Comput. Sci. 399(1), 141\u2013156 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9484_CR29","first-page":"1250","volume-title":"Proc. IEEE International Conference on Robotics and Automation","author":"R. Kurazume","year":"1994","unstructured":"Kurazume, R., Nagata, S.: Cooperative positioning with multiple robots. In: Proc. IEEE International Conference on Robotics and Automation, pp. 1250\u20131257 (1994)"},{"key":"9484_CR30","volume-title":"Introduction to Parallel Algorithms and Architectures","author":"F.T. Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, San Mateo (1992)"},{"key":"9484_CR31","volume-title":"R\u00e9cr\u00e9ations Math\u00e9matiques","author":"\u00c9. Lucas","year":"1883","unstructured":"Lucas, \u00c9.: R\u00e9cr\u00e9ations Math\u00e9matiques vol.\u00a02. Gauthier-Villars, Paris (1883). Sixi\u00e8me r\u00e9cr\u00e9ation: Les jeux de demoiselles"},{"issue":"1","key":"9484_CR32","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TC.1979.1675216","volume":"100","author":"D. Nassimi","year":"1979","unstructured":"Nassimi, D., Sahni, S.: Bitonic sort on a mesh-connected parallel computer. IEEE Trans. Comput. 100(1), 2\u20137 (1979)","journal-title":"IEEE Trans. Comput."},{"key":"9484_CR33","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D. Rater","year":"1990","unstructured":"Rater, D., Warmuth, M.: Finding a shortest solution for the nxn extension of the 15-puzzle is intractable. J. Symb. Comput. 10, 111\u2013137 (1990)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"9484_CR34","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1287\/opre.31.3.507","volume":"31","author":"H. Ratliff","year":"1983","unstructured":"Ratliff, H., Rosenthal, A.: Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem. Oper. Res. 31(3), 507\u2013521 (1983)","journal-title":"Oper. Res."},{"key":"9484_CR35","first-page":"241","volume-title":"Proc. 5th International Symposium on Distributed and Autonomous Robotic Systems (DARS)","author":"I.M. Rekleitis","year":"2000","unstructured":"Rekleitis, I.M., Dudek, G., Milios, E.E.: Graph-based exploration using multiple robots. In: Proc. 5th International Symposium on Distributed and Autonomous Robotic Systems (DARS), pp. 241\u2013250 (2000)"},{"issue":"2","key":"9484_CR36","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1109\/12.16500","volume":"38","author":"I. Scherson","year":"1989","unstructured":"Scherson, I., Sen, S.: Parallel sorting in two-dimensional VLSI models of computation. IEEE Trans. Comput. 38(2), 238\u2013249 (1989)","journal-title":"IEEE Trans. Comput."},{"key":"9484_CR37","first-page":"852","volume-title":"Proc. National Conference on Artificial Intelligence (AAAI)","author":"R. Simmons","year":"2000","unstructured":"Simmons, R., Apfelbaum, D., Burgard, W., Fox, D., Moors, M., Thrun, S., Younes, H.: Coordination for multi-robot exploration and mapping. In: Proc. National Conference on Artificial Intelligence (AAAI), pp. 852\u2013858 (2000)"},{"key":"9484_CR38","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1109\/ROBOT.1993.292155","volume-title":"Proc. IEEE International Conference on Robotics and Automation (ICRA)","author":"K. Singh","year":"1993","unstructured":"Singh, K., Fujimura, K.: Map making by cooperating mobile robots. In: Proc. IEEE International Conference on Robotics and Automation (ICRA), pp. 254\u2013259 (1993)"},{"issue":"4","key":"9484_CR39","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1137\/S009753979628292X","volume":"28","author":"I. Suzuki","year":"1999","unstructured":"Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347\u20131363 (1999)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9484_CR40","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1016\/j.orl.2010.08.008","volume":"38","author":"P. van\u2019t Hof","year":"2010","unstructured":"van\u2019t Hof, P., Post, G., Briskorn, D.: Constructing fair round robin tournaments with a minimum number of breaks. Oper. Res. Lett. 38(6), 592\u2013596 (2010)","journal-title":"Oper. Res. Lett."},{"issue":"5","key":"9484_CR41","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1109\/70.795795","volume":"15","author":"I. Wagner","year":"1999","unstructured":"Wagner, I., Lindenbaum, M., Bruckstein, A.: Distributed covering by ant-robots using evaporating traces. IEEE Trans. Robot. Autom. 15(5), 918\u2013933 (1999)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"9484_CR42","first-page":"1045","volume-title":"Proc. IEEE International Conference on Robotics and Automation (ICRA)","author":"J. Wang","year":"1994","unstructured":"Wang, J.: On sign-board based inter-robot communication in distributed robotic systems. In: Proc. IEEE International Conference on Robotics and Automation (ICRA), pp. 1045\u20131050 (1994)"},{"issue":"1","key":"9484_CR43","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","volume":"16","author":"R.M. Wilson","year":"1974","unstructured":"Wilson, R.M.: Graph puzzles, homotopy, and the alternating group. J. Comb. Theory, Ser. B 16(1), 86\u201396 (1974)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9484_CR44","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/280765.280773","volume-title":"Proc. 2nd International Conference on Autonomous Agents","author":"B. Yamauchi","year":"1998","unstructured":"Yamauchi, B.: Frontier-based exploration using multiple robots. In: Proc. 2nd International Conference on Autonomous Agents, pp. 47\u201353 (1998)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9484-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9484-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9484-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T03:07:58Z","timestamp":1563073678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9484-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,25]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["9484"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9484-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,25]]}}}