{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:18:08Z","timestamp":1725891488874},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642303463"},{"type":"electronic","value":"9783642303470"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30347-0_6","type":"book-chapter","created":{"date-parts":[[2012,5,31]],"date-time":"2012-05-31T02:27:55Z","timestamp":1338431275000},"page":"28-39","source":"Crossref","is-referenced-by-count":0,"title":["The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye"],"prefix":"10.1007","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","reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1002\/nav.10011","volume":"49","author":"S. Alpern","year":"2002","unstructured":"Alpern, S.: Rendezvous search on labeled networks. Naval Research Logistics\u00a049(3), 256\u2013274 (2002)","journal-title":"Naval Research Logistics"},{"issue":"1","key":"6_CR2","doi-asserted-by":"publisher","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. Journal of Applied Probability\u00a036(1), 223\u2013231 (1999)","journal-title":"Journal of Applied Probability"},{"issue":"3","key":"6_CR3","doi-asserted-by":"publisher","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 Applied Mathematics\u00a055(3), 197\u2013218 (1994)","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Arkin, R.: Motor schema-based mobile robot navigation. In: Proc. IEEE Conference on Robotics and Automation, pp. 264\u2013271 (1987)","key":"6_CR4"},{"issue":"6","key":"6_CR5","doi-asserted-by":"publisher","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 Transactions on Robotics and Automation\u00a014(6), 926\u2013939 (1998)","journal-title":"IEEE Transactions on Robotics and Automation"},{"doi-asserted-by":"crossref","unstructured":"Balch, T., Hybinette, M.: Behavior-based coordination of large-scale robot formations. In: Proc. 4th International Conference on MultiAgent Systems, pp. 363\u2013364 (2000)","key":"6_CR6","DOI":"10.1109\/ICMAS.2000.858476"},{"doi-asserted-by":"crossref","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":"6_CR7","DOI":"10.1007\/978-4-431-65941-9_37"},{"doi-asserted-by":"crossref","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.\u00a01, pp. 476\u2013481 (2000)","key":"6_CR8","DOI":"10.1109\/ROBOT.2000.844100"},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 1181\u20131196. Springer, Heidelberg (2003)"},{"unstructured":"Culberson, J., Schaeffer, J.: Efficiently searching the 15-puzzle. Technical report, Department of Computing Science, University of Alberta (1994)","key":"6_CR10"},{"doi-asserted-by":"crossref","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)","key":"6_CR11","DOI":"10.1145\/1835698.1835761"},{"key":"6_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-540-39658-1_19","volume-title":"Algorithms - ESA 2003","author":"A. Dessmark","year":"2003","unstructured":"Dessmark, A., Fraigniaud, P., Pelc, A.: Deterministic Rendezvous in Graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 184\u2013195. Springer, Heidelberg (2003)"},{"doi-asserted-by":"crossref","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)","key":"6_CR13","DOI":"10.1109\/IVS.2000.898389"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-44693-1_22","volume-title":"STACS 2001","author":"P. Flocchini","year":"2001","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of Asynchronous Oblivious Robots with Limited Visibility. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 247\u2013258. Springer, Heidelberg (2001)"},{"doi-asserted-by":"crossref","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)","key":"6_CR15","DOI":"10.1145\/800113.803626"},{"unstructured":"Gervasi, V., Prencipe, G.: Need a fleet? Use the force! In: Proc. 2nd International Conference on Fun With Algorithms (FUN), pp. 149\u2013164 (2001)","key":"6_CR16"},{"issue":"4","key":"6_CR17","first-page":"469","volume":"6","author":"J. Gudmundsson","year":"1999","unstructured":"Gudmundsson, J., Levcopoulos, C.: A fast approximation algorithm for TSP with neighborhoods. Nordic Journal of Computing\u00a06(4), 469 (1999)","journal-title":"Nordic Journal of Computing"},{"issue":"1-2","key":"6_CR18","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0343(1-2), 72\u201396 (2005)","journal-title":"Theoretical Computer Science"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/3-540-45465-9_35","volume-title":"Automata, Languages and Programming","author":"R.A. Hearn","year":"2002","unstructured":"Hearn, R.A., Demaine, E.D.: The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 401\u2013413. Springer, Heidelberg (2002)"},{"doi-asserted-by":"crossref","unstructured":"Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. A K Peters, Ltd. (2009)","key":"6_CR20","DOI":"10.1201\/b10581"},{"issue":"4","key":"6_CR21","doi-asserted-by":"publisher","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. The International Journal of Robotics Research\u00a03(4), 76\u201388 (1984)","journal-title":"The International Journal of Robotics Research"},{"unstructured":"Hordern, E.: Sliding Piece Puzzles. Oxford University Press (1986)","key":"6_CR22"},{"issue":"2","key":"6_CR23","doi-asserted-by":"publisher","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. Autonomous Robots\u00a013(2), 113\u2013126 (2002)","journal-title":"Autonomous Robots"},{"doi-asserted-by":"crossref","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":"6_CR24","DOI":"10.1007\/978-4-431-65941-9_30"},{"doi-asserted-by":"crossref","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 (2004)","key":"6_CR25","DOI":"10.1007\/978-3-540-45058-0_6"},{"issue":"3","key":"6_CR26","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1145\/136035.136037","volume":"24","author":"Y. Hwang","year":"1992","unstructured":"Hwang, Y., Ahuja, N.: Gross motion planning a survey. ACM Computing Surveys (CSUR)\u00a024(3), 219\u2013291 (1992)","journal-title":"ACM Computing Surveys (CSUR)"},{"unstructured":"Karlemo, F., \u00d6sterg\u00e5rd, P.: On sliding block puzzles. Journal of Combinatorial Mathematics and Combinatorial Computing (2000)","key":"6_CR27"},{"key":"6_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/11780823_5","volume-title":"Structural Information and Communication Complexity","author":"D.R. Kowalski","year":"2006","unstructured":"Kowalski, D.R., Malinowski, A.: How to Meet in Anonymous Network. In: Flocchini, P., G\u0105sieniec, L. (eds.) SIROCCO 2006. LNCS, vol.\u00a04056, pp. 44\u201358. Springer, Heidelberg (2006)"},{"doi-asserted-by":"crossref","unstructured":"Kurazume, R., Nagata, S.: Cooperative positioning with multiple robots. In: Proceedings of 1994 IEEE International Conference on Robotics and Automation, pp. 1250\u20131257. IEEE (1994)","key":"6_CR29","DOI":"10.1109\/ROBOT.1994.351315"},{"unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann Publishers (1992)","key":"6_CR30"},{"issue":"1","key":"6_CR31","doi-asserted-by":"publisher","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 Transactions on Computers\u00a0100(1), 2\u20137 (1979)","journal-title":"IEEE Transactions on Computers"},{"key":"6_CR32","doi-asserted-by":"publisher","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. Journal of Symbolic Computation\u00a010, 111\u2013137 (1990)","journal-title":"Journal of Symbolic Computation"},{"doi-asserted-by":"crossref","unstructured":"Ratliff, H., Rosenthal, A.: Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem. Operations Research, 507\u2013521 (1983)","key":"6_CR33","DOI":"10.1287\/opre.31.3.507"},{"doi-asserted-by":"crossref","unstructured":"Rekleitis, I.M., Dudek, G., Milios, E.E.: Graph-based exploration using multiple robots. In: 5th International Symposium on Distributed and Autonomous Robotic Systems, pp. 241\u2013250. Springer (2000)","key":"6_CR34","DOI":"10.1007\/978-4-431-67919-6_23"},{"issue":"2","key":"6_CR35","doi-asserted-by":"publisher","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 Transactions on Computers\u00a038(2), 238\u2013249 (1989)","journal-title":"IEEE Transactions on Computers"},{"unstructured":"Simmons, R., Apfelbaum, D., Burgard, W., Fox, D., Moors, M., Thrun, S., Younes, H.: Coordination for multi-robot exploration and mapping. In: Proceedings National Conference on Artificial Intelligence, pp. 852\u2013858. AAAI Press, MIT Press, Menlo Park, Cambridge (1999, 2000)","key":"6_CR36"},{"doi-asserted-by":"crossref","unstructured":"Singh, K., Fujimura, K.: Map making by cooperating mobile robots. In: Proceedings of 1993 IEEE International Conference on Robotics and Automation (ICRA), pp. 254\u2013259 (1993)","key":"6_CR37","DOI":"10.1109\/ROBOT.1993.292155"},{"issue":"4","key":"6_CR38","doi-asserted-by":"publisher","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.\u00a028(4), 1347\u20131363 (1999)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"6_CR39","doi-asserted-by":"publisher","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 Transactions on Robotics and Automation\u00a015(5), 918\u2013933 (1999)","journal-title":"IEEE Transactions on Robotics and Automation"},{"doi-asserted-by":"crossref","unstructured":"Wang, J.: On sign-board based inter-robot communication in distributed robotic systems. In: Proc. 1994 IEEE International Conference on Robotics and Automation, pp. 1045\u20131050 (1994)","key":"6_CR40","DOI":"10.1109\/ROBOT.1994.351219"},{"issue":"1","key":"6_CR41","doi-asserted-by":"publisher","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. Journal of Combinatorial Theory, Series B\u00a016(1), 86\u201396 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"},{"doi-asserted-by":"crossref","unstructured":"Yamauchi, B.: Frontier-based exploration using multiple robots. In: Proc. 2nd International Conference on Autonomous Agents, pp. 47\u201353 (1998)","key":"6_CR42","DOI":"10.1145\/280765.280773"}],"container-title":["Lecture Notes in Computer Science","Fun with Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30347-0_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:58Z","timestamp":1606187158000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30347-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642303463","9783642303470"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30347-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}