The kissing problem: how to end a gathering when everyone kisses everyone else goodbye

DOI10.1007/s00224-013-9484-xzbMath1303.68152OpenAlexW1976694430MaRDI QIDQ489765

Ritwik Bose, Michael A. Bender, Samuel McCauley, Rezaul Alam Chowdhury

Publication date: 21 January 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9484-x

zbMATH Keywords

algorithmscommunicationapproximation algorithmsroutingblock slidingkissing problem

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gathering of asynchronous robots with limited visibility
• Constructing fair round robin tournaments with a minimum number of breaks
• The \((n^ 2-1)\)-puzzle and related relocation problems
• How to meet in anonymous network
• Approximation algorithms for the Geometric Covering Salesman Problem
• Coordination without communication: the case of the flocking problem
• Graph puzzles, homotopy, and the alternating group
• Deterministic rendezvous in graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• Parallel sorting in two-dimensional VLSI models of computation
• Bitonic Sort on a Mesh-Connected Parallel Computer
• Rendezvous search on a graph
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Rendezvous search on labeled networks
• On the computational power of oblivious robots