Algorithm Theory - SWAT 2010

ThisvolumecontainsthepaperspresentedatSWAT2010,the12thScandinavian Symposium on Algorithm Theory. Since 1988 SWAT has been held biennially in the Nordic countries; it has a loose association with WADS (Workshop on Algorithms and Data Structures) that is held on odd-numbered years in North America. This 12th SWAT was held during June 21-23, at the University of Bergen in Norway. The conference focuses on algorithms and data structures. The call for - pers invited contributions in all areas of algorithms and data structures, incl- ing approximation algorithms, computational biology, computational geometry, distributedalgorithms,external-memoryalgorithms,graphalgorithms,online- gorithms, optimization algorithms, parallel algorithms, randomized algorithms, stringalgorithmsandalgorithmicgametheory.Atotalof78papersweresubm- ted,outofwhichtheProgramCommitteeselected36forpresentationatthes- posium.Inaddition,invitedlecturesweregivenbySanjeevArorafromPrinceton University, PrabhakarRaghavanfrom Yahoo! ResearchLabs, and Dana Randall from Georgia Institute of Technology. Wewouldliketo thankallthepeoplewho contributedto makingSWAT 2010 a success.In particular, we thank the Program Committee and all of our many colleagues who helped the committee evaluate the submissions. We also thank the NorwegianResearch Council and the University of Bergen for their support.