Fun with Algorithms [Ferro, Luccio & Widmayer 2014-05-16].pdf

(13584 KB) Pobierz
Alfredo Ferro
Fabrizio Luccio
Peter Widmayer
(Eds.)
LNCS 8496
Fun with
Algorithms
7th International Conference, FUN 2014
Lipari Island, Sicily, Italy, July 1–3, 2014
Proceedings
123
Lecture Notes in Computer Science
Commenced Publication in 1973
Founding and Former Series Editors:
Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
8496
Editorial Board
David Hutchison
Lancaster University, UK
Takeo Kanade
Carnegie Mellon University, Pittsburgh, PA, USA
Josef Kittler
University of Surrey, Guildford, UK
Jon M. Kleinberg
Cornell University, Ithaca, NY, USA
Alfred Kobsa
University of California, Irvine, CA, USA
Friedemann Mattern
ETH Zurich, Switzerland
John C. Mitchell
Stanford University, CA, USA
Moni Naor
Weizmann Institute of Science, Rehovot, Israel
Oscar Nierstrasz
University of Bern, Switzerland
C. Pandu Rangan
Indian Institute of Technology, Madras, India
Bernhard Steffen
TU Dortmund University, Germany
Demetri Terzopoulos
University of California, Los Angeles, CA, USA
Doug Tygar
University of California, Berkeley, CA, USA
Gerhard Weikum
Max Planck Institute for Informatics, Saarbruecken, Germany
Alfredo Ferro Fabrizio Luccio
Peter Widmayer (Eds.)
Fun with
Algorithms
7th International Conference, FUN 2014
Lipari Island, Sicily, Italy, July 1-3, 2014
Proceedings
13
Volume Editors
Alfredo Ferro
Università degli Studi di Catania
Dipartimento di Matematica e Informatica,
Viale A. Doria 6, 95125 Catania, Italy
E-mail: ferro@dmi.unict.it
Fabrizio Luccio
Università di Pisa, Dipartimento di Informatica
Largo B. Pontecorvo 3, 56127 Pisa, Italy
E-mail: luccio@di.unipi.it
Peter Widmayer
ETH Zürich, Institute of Theoretical Computer Science
Universitätsstrasse 6, 8092 Zürich, Switzerland
E-mail: widmayer@inf.ethz.ch
ISSN 0302-9743
e-ISSN 1611-3349
ISBN 978-3-319-07889-2
e-ISBN 978-3-319-07890-8
DOI 10.1007/978-3-319-07890-8
Springer Cham Heidelberg New York Dordrecht London
Library of Congress Control Number: 2014940050
LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues
© Springer International Publishing Switzerland 2014
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of
the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,
broadcasting, reproduction on microfilms or in any other physical way, and transmission or information
storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology
now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection
with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and
executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication
or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location,
in ist current version, and permission for use must always be obtained from Springer. Permissions for use
may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution
under the respective Copyright Law.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
While the advice and information in this book are believed to be true and accurate at the date of publication,
neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or
omissions that may be made. The publisher makes no warranty, express or implied, with respect to the
material contained herein.
Typesetting:
Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India
Printed on acid-free paper
Springer is part of Springer Science+Business Media (www.springer.com)
Preface
FUN with Algorithms is dedicated to the use, design, and analysis of algorithms
and data structures, focusing on results that provide amusing, witty but nonethe-
less original and scientifically profound contributions to the area. Donald Knuth’s
famous quote captures this spirit nicely: .... pleasure has probably been the
main goal all along. But I hesitate to admit it, because computer scientists want
to maintain their image as hard-working individuals who deserve high salaries.
Sooner or later society will realise that certain kinds of hard work are in fact
admirable even though they are more fun than just about anything else.” The
previous FUNs were held in Elba Island, Italy; in Castiglioncello, Tuscany, Italy;
in Ischia Island, Italy; and in San Servolo Island, Venice, Italy. Special issues
of
Theoretical Computer Science, Discrete Applied Mathematics,
and
Theory of
Computing Systems
were dedicated to them.
This volume contains the papers presented at the 7th International Con-
ference on Fun with Algorithms 2014 that was held during July 1–3, 2014, on
Lipari Island, Italy. The call for papers attracted 49 submissions from all over the
world, addressing a wide variety of topics, including algorithmic questions rooted
in biology, cryptography, game theory, graphs, the Internet, robotics and mobil-
ity, combinatorics, geometry, stringology, as well as space-conscious, randomized,
parallel, distributed algorithms, and their visualization. Each submission was re-
viewed by three Program Committee members. After a careful reviewing process
and a thorough discussion, the committee decided to accept 29 papers. In addi-
tion, the program featured two invited talks by Paolo Boldi and Erik Demaine.
Extended versions of selected papers will appear in a special issue of the journal
Theoretical Computer Science.
We thank all authors who submitted their work to FUN 2014, all Program
Committee members for their expert assessments and the ensuing discussions,
all external reviewers for their kind help, and Alfredo Ferro, Rosalba Giugno,
Alfredo Pulvirenti as well as Giuseppe Prencipe for the organization of the con-
ference and everything around it.
We used EasyChair
(http://www.easychair.org/)
throughout the entire
preparation of the conference, for handling submissions, reviews, the selection of
papers, and the production of this volume. It greatly facilitated the whole pro-
cess. We want to warmly thank the people who designed it and those who main-
tain it. Warm thanks also go to Alfred Hofmann and Ingrid Haas at

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin