Algorithm Theory – SWAT 2008

The Scandinavian Workshop on Algorithm Theory (SWAT) is a biennial int- national conferenceintended as a forum for researchersin the area of design and analysisofalgorithmsanddatastructures. The?rstSWATworkshopwasheldin Halmstad, Sweden, in 1988. Since then it has been held biennially, rotating - tween the ?ve Nordic countries - Denmark, Finland, Iceland, Norway and S- den, with the exception of 2006 when it was in Riga. Earlier SWATs were held in Humlebaek, Denmark (2004), Turku, Finland (2002), Bergen, Norway (2000), ? Stockholm, Sweden (1998), Reykjavik, Iceland (1996), Arhus, Denmark (1994), Helsinki,Finland(1992),Bergen,Norway(1990)andHalmstad,Sweden(1988). This volume contains the contributed papers presented at the 11th Sc- dinavian Workshop on Algorithm Theory (SWAT 2008), held in Gothenburg, Sweden, July 2-4, 2008. In addition, the volume also includes abstracts of an invited talk by Michael Mitzenmacher on "A Survey of Results for Deletion Channels and Related Synchronization Channels"and by Vijay V. Vazirani on "Nash Bargaining via Flexible Budget Markets. " Papers were solicited for original research on algorithms and data structures in all areas, including but not limited to: approximation algorithms, compu- tionalbiology,computationalgeometry,distributedalgorithms,external-memory algorithms,graphalgorithms,online algorithms,optimization algorithms,par- lel algorithms, randomized algorithms, string algorithms and algorithmic game theory. The 36 contributed papers were chosen from 111 submissions. Revised and expanded versions of selected papers will be considered for publication in a special issue of Algorithmica. The best paper award was given to Yossi Azar, Uriel Feige and Daniel Glasner for their paper "A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. " Eachpaperwasreviewedbyatleastthreereferees,andevaluatedonthequ- ity,originalityandrelevanceto the symposium.