Fun with Algorithms - FUN 2007. Proceedings of the 4th International Conference

This volume contains the papers presented at the Fourth International Conference on Fun with Algorithms (FUN 2007), held June 3–5, 2007 in the beautiful Tuscanian coastal town of Castiglioncello, Italy. FUN is a three-yearly conference 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. The previous three meetings were held on Elba Island, Italy, and special issues of the journals Theoretical Computer Science (FUN 1998), Discrete Applied Mathematics (FUN 2001), and Theory of Computing Systems (FUN 2004) feature extended versions of selected papers from the three conference programs. In response to the Call for Papers for FUN 2007, we received 41 submissions from 25 countries. Each submission was reviewed by at least three Program Committee members. At the end of the selection process, the committee decided to accept 20 papers. The program also includes three invited talks by Giuseppe Di Battista (U. Rome III, Italy), Nicola Santoro (Carleton U., Canada), and Luca Trevisan (U.C. Berkeley, USA). We wish to thank all the authors who submitted their papers to FUN 2007 and thus contributed to the creation of a high-quality program and entertaining meeting, as well as the colleagues who accepted to serve on the Program Committee and provided invaluable help with the reviewing process. We also wish to thank the external reviewers (listed on the following pages) including those who completed urgent reviews during the discussion phase. Paper submission, selection, and generation of the proceedings was greatly eased by the use of the publicdomain EasyChair Conference System (http://www.easychair.org).We wish to thank the EasyChair creators and maintainers for their selfless committment to the scientific community. Finally, special thanks go to Vincenzo Gervasi, whose constant help and dedication was crucial in making FUN 2007 a successful event.