Algorithms and Computation

The papers in this volume were selected for presentation at the Ninth Annual International Symposium on Algorithms and Computation (ISAAC¿98),heldonDecember14¿16,1998inTaejon,Korea.P- viousmeetingswereheldinTokyo(1990),Taipei(1991),Nagoya (1992),HongKong(1993),Beijing(1994),Cairns(1995),Osaka (1996),andSingapore(1997). The symposium was jointly sponsored by Korea Advanced - stitute of Science and Technology (KAIST) and Korea Information Science Society (KISS) to commemorate its 25th anniversary in - operationwithMinistryofInformationandCommunication,Korea InformationSocietyDevelopmentInstitute,andKoreaScienceand Engineering Foundation. Inresponsetothecallforpapers,102extendedabstractswere submitted from 21 countries. Each submitted paper was reported on byatleastfourprogramcommitteemembers,withtheassistance ofreferees,asindicatedbytherefereelistfoundintheseproce- ings. There were many more acceptable papers than there was space availableinthesymposiumschedule,andtheprogramcommittee¿s task was extremely di?cult. The 47 papers selected for presentation hadatotalof105authors,residentasfollows:Japan24,Germany 17,UnitedStateofAmerica15,Taiwan10,HongKongandKorea 6each,Spain5,SwitzerlandandAustralia4each,Austria,Canada, andFrance3each,ItalyandNetherlands2each,andGreece1. We thank all program committee members and their referees fortheirexcellentwork,especiallygiventhedemandingtimec- straints; they gave the symposium its distinctive character. We thank all who submitted papers for consideration: they all contributed to the high quality of the symposium. Finally,wethankallthepeoplewhoworkedhardtoputinplace the logistical arrangements of the symposium ¿ our colleagues and our graduate students. It is their hard work that made the sym- sium possible and enjoyable.