Algorithms -- ESA 2004

This volume contains the 70 contributed papers and abstracts of two invited l- tures presented at the 12th Annual European Symposium on Algorithms (ESA 2004), held in Bergen, Norway, September 14–17, 2004. The papers in each s- tion of the proceedi... Read more

This volume contains the 70 contributed papers and abstracts of two invited l- tures presented at the 12th Annual European Symposium on Algorithms (ESA 2004), held in Bergen, Norway, September 14–17, 2004. The papers in each s- tion of the proceedings are arranged alphabetically. The three distinguished - vited speakers were David Eppstein, Michael Fellows and Monika Henzinger. As in the last two years, ESA had two tracks, with separate program c- mittees, which dealt respectively with: – the design and mathematical analysis of algorithms (the “Design and A- lysis” track); – real-world applications, engineering and experimental analysis of algorithms (the “Engineering and Applications” track). Previous ESAs were held at Bad Honnef, Germany (1993); Utrecht, The Netherlands (1994); Corfu, Greece (1995); Barcelona, Spain (1996); Graz, A- tria (1997); Venice, Italy (1998); Prague, Czech Republic (1999); Saarbruc ¨ ken, ? Germany (2000); Arhus, Denmark (2001); Rome, Italy (2002); and Budapest, Hungary (2003). The predecessor to the Engineering and Applications track of ESA was the annual Workshop on Algorithm Engineering (WAE). Previous WAEs were held in Venice, Italy (1997); Saarbruc ¨ ken, Germany (1998); London, ? UK (1999); Saarbruc ¨ ken, Germany (2000); and Arhus, Denmark (2001). The proceedings of the previous ESAs were published as Springer-Verlag’s LNCS volumes 726, 855, 979, 1284, 1461, 1643, 1879, 2161, 2461, and 2832. The proceedingsoftheWAEsfrom1999onwardswerepublishedasSpringer-Verlag’s LNCS volumes 1668, 1982, and 2141. Less