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 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.