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

DOI10.1007/S00224-013-9484-XMaRDI QIDQ489765zbMATH OpenOpenAlexFDO

Authors Michael A. Bender, Ritwik Bose, 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)

Recommendations

• The Kissing Number of the Square
• New formulations for the Kissing Number Problem
• Forming all pairs in a minimal number of steps
• An efficient algorithm for the “stable roommates” problem
• The rendezvous problem on discrete locations

Cites work

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

Cited in

(1)

• Excuse me! or the courteous theatregoers' problem

This page was built for publication: The kissing problem: how to end a gathering when everyone kisses everyone else goodbye

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489765)