Lecture Notes in Computer Science

This volume contains the proceedings of the Twelfth Annual International S- posiumonAlgorithmsandComputation(ISAAC2001),heldinChristchurch, NewZealand,19-21December2001. Inthepast,ithasbeenheldinTokyo(1990), Taipei(1991),Nagoya(1992),HongKong(1994),Cairnes(1995),Osaka(1996), Singapore(1997),Taejon,Korea(1998),Madras(1999),andTaipei(2000). Since thethirdinNagoya,theproceedingshavebeenpublishedinSpringer-Verlag's Lecture Notes in Computer Science series. AlthoughthesymposiumrotatesmainlyintheAsia/Paci?cregion,ther- ereeingprocesswasconductedinternationally,andresearchersgatheredfrom allovertheworld. Wereceived124submissionsfrom32countries,ofwhich 62 papers were accepted for presentation at the symposium. The papers of three invited speakers are also included. Submission was conducted electro- cally by CyberChair generously o?ered by the University of Twente. Each paper was reviewed by three or four referees with the assistance of external referees, whose names are listed overleaf. Discussions on how to select papers were also conducted electronically over more than a week. Due to the large number of submittedpapers,thereviewingprocesswasquitechallengingfortheprogram committee. There were many acceptable papers which we could not accom- date into the time frame of the three-day symposium. The best paper award was given to "Computing the Quartet Distance between Evolutionary Trees in Time 2 O(nlog n)"byGerthSt¸ltingBrodal,RolfFagerberg,andChristianN¸rgaard Storm Pedersen. We hope all accepted papers will eventually appear in scienti?c journals in a more polished form. IntheeraoftheInternet,wetendtothinkwecanexchangeideaswith other researchers instantly without needing to meet. This way we tend to be isolatedunknowingly. BecauseoftheInternet,however,theneedformeeting otherpeoplefacetofaceiseverincreasing. Todoresearch,itisstillbestto seeourpeersdirectly,andgetideasfromtheveryinventers. WehopeISAAC 2001 made a good forum for researchers in algorithms and computation to meet, beingheldinNewZealand,abeautifulsmallnationof3. 8millionpeople. Itis roughlyatthecenterofthewaterhemisphere,meaningthatitisfarthestfrom therestoftheworld. Peoplecanescapefromtheirdailybusinesses,meetpeople, and refresh their thinking. We thank all the authors who submitted papers and contributed to the high quality of the symposium. We thank all the organizing committee members, programcommitteemembers,andexternalrefereeswhosacri?cedtheirtime for the symposium. We thank all the sponsors who made the symposium ?n- ciallyviable.