This volume contains the proceedings of the 21st Annual International Symposium on Algorithms and Computations (ISAAC 2010), held in Jeju, Korea during December 15–17, 2010. Past editions have been held in Tokyo, Taipei, Nagoya, Hong Kong, Beijing, Cairns, Osaka, Singapore, Taejon, Chennai, Taipei, Christchurch, Vancouver, Kyoto, Hong Kong, Hainan, Kolkata, Sendai, Gold Coast, and Hawaii over the years 1990-2009.
ISAAC is an annual international symposium that covers the very wide range of topics in algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in algorithms and the theory of computation where they can exchange ideas in this active research community.
In response to the call for papers, ISAAC 2010 received 182 papers. Each submission was reviewed by at least three Program Committee members with the assistance of external referees. Since there were many high-quality papers, the Program Committee’s task was extremely difficult. Through an extensive discussion, the Program Committee accepted 77 of the submissions to be presented at the conference. Two special issues, one of Algorithmica and one of the International Journal of Computational Geometry and Applications, were prepared with selected papers from ISAAC 2010.
The best paper award was given to “From Holant to #CSP and Back: Dichotomy for Holantc Problems” by Jin-Yi Cai, Sangxia Huang and Pinyan Lu, and the best student paper award to “Satisfiability with Index Dependency” by Hongyu Liang and Jing He. Two eminent invited speakers, David Eppstein from University of California, Irvine, and Matt Franklin from University of California, Davis, also contributed to this volume.
We would like to thank all Program Committee members and external referees for their excellent work, especially given the demanding time constraints; they gave the conference its distinctive character. We thank all who submitted papers for consideration; they all contributed to the high quality of the conference. We also thank the Organizing Committee members for their dedicated contribution that made the conference possible and enjoyable. Finally, we thank our sponsor SIGTCS (Special Interest Group on the Theoretical Computer Science) of KIISE (The Korean Institute of Information Scientists and Engineers) for the assistance and support.