Lecture Notes in Computer Science 2518 EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Tokyo Prosenjit Bose Pat Morin (Eds.) Algorithms and Computation 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditors ProsenjitBose PatMorin CarletonUniversity,SchoolofComputerScience 1125ColonelByDrive,Ottawa,Ontario,Canada,K1S5B6 E-mail:{jit,morin}@scs.carleton.ca Cataloging-in-PublicationDataappliedfor AcatalogrecordforthisbookisavailablefromtheLibraryofCongress BibliographicinformationpublishedbyDieDeutscheBibliothek DieDeutscheBibliothekliststhispublicationintheDeutscheNationalbibliographie; detailedbibliographicdataisavailableintheInternetat<http://dnb.ddb.de>. CRSubjectClassification(1998):F.2,F.1,C.2,G.2-3,I.3.5,F.1 ISSN0302-9743 ISBN3-540-00142-5Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagBerlinHeidelbergNewYork amemberofBertelsmannSpringerScience+BusinessMediaGmbH http://www.springer.de ©Springer-VerlagBerlinHeidelberg2002 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyPTP-Berlin,StefanSossnae.K. Printedonacid-freepaper SPIN:10871021 06/3142 543210 Preface ThisvolumecontainsthepapersselectedforpresentationattheThirteenthAn- nual International Symposium on Algorithms and Computation (ISAAC 2002) tobeheldinVancouver,CanadaonNovember21-23,2002.Thisisthefirsttime that ISAAC has ventured into North America, as it is traditionally held in the Asia-Pacific region. ISAAC is an annual international symposium that covers the very broad areas of algorithms and computing in general. The scope of this symposium in- cludes both theoretical and applied research from these fields. The main aim of the symposium is to promote the exchange of ideas in this active research community. The specific themes targeted for ISAAC 2002 were Computational Geometry,AlgorithmsandDataStructures,ApproximationAlgorithms,Rando- mized Algorithms, Graph Drawing and Graph Algorithms, Combinatorial Op- timization,ComputationalBiology,ComputationalFinance,Cryptography,and Parallel and Distributed Computing. In response to our call for papers, we received close to 160 submissions. The challenging task of selecting the papers for presentation was performed by the members of our program committee, their support staff, and referees. All of them deserve special thanks for their hard work in the difficult task of selecting a mere 54 papers from the high-quality submissions. Unfortunately, due to the timeconstraintsimposedbyathree-dayconference,wewereforcedtoturnaway many excellent papers. JohnIaconowillreceivethetraditionalbestpaperawardforhispaperentitled Key Independent Optimality. Our three invited speakers are Luc Devroye from McGill University who will speak on Random Tries, Ja´nos Pach from New York University who will speak on Monotone Drawings of Planar Graphs, and Nicho- las Pippenger from the University of British Columbia who will speak on the Expected Acceptance Counts for Finite Automata with Almost Uniform Input. No conference can succeed without exceptional local organization. For the often overlooked and thankless task of finding a suitable venue and banquet location,dealingwiththelogisticsofregistration,organizinglunchesandcoffee, etc.,wewouldliketothankthetheorganizingcommittee,NadjaRence,andOlga Stachova for all their efforts above and beyond the call of duty. We thank our sponsorsSimonFraserUniversity,thePacificInstituteofMathematicalSciences, theinstituteforMathematicsofInformationTechnologyandComplexSystems, and Bajai Inc. for their generous support. Finally, we thank all the authors and participants. We hope this edition of ISAAC will be a success. August 2002 Prosenjit Bose Pat Morin Organization Organizing Committee Binay Bhattacharya (Simon Fraser University, Canada) Prosenjit Bose (Carleton University, Canada) Arvind Gupta (Simon Fraser University, Canada) Tiko Kameda (Simon Fraser University, Canada) Program Committee Prosenjit Bose, Program Chair (Carleton University, Canada) Tetsuo Asano (JAIST, Japan) Binay Bhattacharya (Simon Fraser University, Canada) Hans Bodlaender (Utrecht University, The Netherlands) Rudolf Fleischer (HKUST, Hong Kong) Naveen Garg (IIT Delhi, India) Arvind Gupta (Simon Fraser University, Canada) Wen-Lian Hsu (Academia Sinica, Taiwan) David Kirkpatrick (University of British Columbia, Canada) Danny Krizanc (Wesleyan University, USA) Ming Li (University of Waterloo, Canada) Michael Molloy (University of Toronto, Canada) Pat Morin (Carleton University, Canada) Ian Munro (University of Waterloo, Canada) Lata Narayanan (Concordia University, Canada) Rajeev Raman (University of Leicester, UK) Sunil Shende (Rutgers University, USA) Hisao Tamaki (Meiji University, Japan) Roberto Tamassia (Brown Univeristy, USA) Denis Th´erien (McGill University, Canada) Takeshi Tokuyama (Tohoku University, Japan) Referees Jochen Alber Therese Biedl Richard Anstee Patricia Bouyer Franc¸ois Anton Alex Brodsky Petra Berenbrink David Bryant Anne Berry Claude Crepeau VIII Organization Henri Darmon Jaroslav Opatrny Will Evans Andrzej Proskuroski Paolo Ferragina Pavel Pudlak Tom Friedetzky Jaikumar Radhakrishnan Leszek Gasieniec Md. Saidur Rahman Daya Ram Gaur Rajeev Raman Dhrubajyoti Goswami Suneeta Ramaswami Joachim Gudmundsson S. S. Ravi Hovhannes Harutyunyan Ran Raz Laurie Hendren Udi Rotics Lisa Higham Pranab Sen Dawei Hong Jiri Sgall Tsan-sheng Hsu Akiyoshi Shioura John Iacono Hiroki Shizuya Klaus Jansen Michiel Smid Juha Kaerkkainen Jack Snoeyink Michael Kaufmann Ting-Yi Sung Rohit Khandekar Chaitanya Swamy Ralf Klasing Richard B. Tan Hirotada Kobayashi Jan Arne Telle Ekkehard Koehler Pascal Tesson Jan Kratochvil Mikkel Thorup Matthias Krause Yosihito Toyama Ramesh Krishnamurti Jacques Vaisey Dietrich Kuske Heribert Vollmer Stefan Langerman Alan Wagner PeiZong Lee Ren´e Weiskircher Hon Fung Li Anthony Whitehead Chi-Jen Lu Gerhard Woeginger Hsueh-I Lu David Wood Wei-Fu Lu 17 additional anonymous referees Cris Moore Sponsors Simon Fraser University Pacific Institute of Mathematical Sciences (PIMS) Mathematics of Information Technology and Complex Systems (MITACS) Bajai Inc. Table of Contents Session 1A Biased Skip Lists .................................................. 1 Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich Space-Efficient Data Structures for Flexible Text Retrieval Systems ...... 14 Kunihiko Sadakane Key Independent Optimality ........................................ 25 John Iacono Session 1B On the Comparison-Addition Complexity of All-Pairs Shortest Paths............................................................. 32 Seth Pettie On the Clique-Width of Graphs in Hereditary Classes .................. 44 Rodica Boliac, Vadim Lozin The Probability of a Rendezvous is Minimal in Complete Graphs ........ 55 Martin Dietzfelbinger Session 2A On the Minimum Volume of a Perturbed Unit Cube.................... 67 Jin-Yi Cai Non-Delaunay-Based Curve Reconstruction ........................... 79 Sumanta Guha, Paula Josiah, Anoop Mittal, Son Dinh Tran Cutting a Country for Smallest Square Fit ............................ 91 Marc van Kreveld, Bettina Speckmann Session 2B On the Emptiness Problem for Two-Way NFA with One Reversal-Bounded Counter .......................................... 103 Zhe Dang, Oscar H. Ibarra, Zhi-Wei Sun Quantum Multi-prover Interactive Proof Systems with Limited Prior Entanglement ..................................................... 115 Hirotada Kobayashi, Keiji Matsumoto X Table of Contents Some Remarks on the L-Conjecture .................................. 128 Qi Cheng Session 3A A Framework for Network Reliability Problems on Graphs of Bounded Treewidth .............................................. 137 Thomas Wolle A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation ..................................................... 150 Anna Galluccio, Guido Proietti Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems .................................................... 163 A. Brandsta¨dt, F.F. Dragan, H.-O. Le, V.B. Le Session 3B An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering ...................................................... 175 Klaus Jansen, Roberto Solis-Oba Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint ........................................................ 187 Markus Bla¨ser, Bodo Manthey A Better Approximation for the Two-Stage Assembly Scheduling Problem with Two Machines at the First Stage ........................ 199 Yoshiyuki Karuno, Hiroshi Nagamochi Session 4A Queaps ........................................................... 211 John Iacono, Stefan Langerman Funnel Heap – A Cache Oblivious Priority Queue ...................... 219 Gerth Stølting Brodal, Rolf Fagerberg Characterizing History Independent Data Structures ................... 229 Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R. Pentney, Emily C. Rocke Session 4B Faster Fixed Parameter Tractable Algorithms for Undirected Feedback Vertex Set................................................ 241 Venkatesh Raman, Saket Saurabh, C. R. Subramanian