Fun with Algorithms: 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007. Proceedings

Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani (auth.), Pierluigi Crescenzi, Giuseppe Prencipe, Geppino Pucci (eds.)3540729135, 9783540729136

This book constitutes the refereed proceedings of the 4th International Conference on Fun with Algorithms, FUN 2007, held in Castiglioncello, Italy in June 2007, co-located with the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2007).

The 20 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 41 submissions. The papers are dedicated to the use, design, and analysis of algorithms and data structures, focusing on results that provide amusing, witty but nonetheless original and scientifically profound contributions to the area.

---

Table of contents :
Front Matter….Pages –
On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features….Pages 1-13
Close Encounters with a Black Hole or Explorations and Gatherings in Dangerous Graphs….Pages 14-14
Fun with Sub-linear Time Algorithms….Pages 15-15
Wooden Geometric Puzzles: Design and Hardness Proofs….Pages 16-29
HIROIMONO Is NP-Complete….Pages 30-39
Tablatures for Stringed Instruments and Generating Functions….Pages 40-52
Knitting for Fun: A Recursive Sweater….Pages 53-65
Pictures from Mongolia – Partial Sorting in a Partial World….Pages 66-77
Efficient Algorithms for the Spoonerism Problem….Pages 78-92
High Spies (or How to Win a Programming Contest)….Pages 93-107
Robots and Demons (The Code of the Origins)….Pages 108-119
The Traveling Beams Optical Solutions for Bounded NP-Complete Problems….Pages 120-134
The Worst Page-Replacement Policy….Pages 135-145
Die Another Day….Pages 146-155
Approximating Rational Numbers by Fractions….Pages 156-165
Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles….Pages 166-182
Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms….Pages 183-197
The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake….Pages 198-212
Drawing Borders Efficiently….Pages 213-226
The Ferry Cover Problem….Pages 227-239
Web Marshals Fighting Curly Link Farms….Pages 240-248
Intruder Capture in Sierpiński Graphs….Pages 249-261
On the Complexity of the Traffic Grooming Problem in Optical Networks….Pages 262-271
Back Matter….Pages –