Lecture Notes in Computer Science 1851 EditedbyG.Goos,J.HartmanisandJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo Magnu´s M. Halldo´rsson (Ed.) Algorithm Theory – SWAT 2000 7th Scandinavian Workshop onAlgorithm Theory Bergen, Norway, July 5-7, 2000 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditor Magnu´sM.Halldo´rsson UniversityofIcelandandUniversityofBergen Taeknigardur,107Reykjavik,Iceland E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Algorithmtheory:proceedings/SWAT’2000,7thScandinavianWorkshop onAlgorithmTheory,Bergen,Norway,July5-7,2000,Magnu´sM. Halldo´rsson(ed.).-Berlin;Heidelberg;NewYork;Barcelona;Hong Kong;London;Milan;Paris;Singapore;Tokyo:Springer,2000 (Lecturenotesincomputerscience;Vol.1851) ISBN3-540-67690-2 CRSubjectClassification(1998):F.2,E.1,G.2,I.3.5,C.2 ISSN0302-9743 ISBN3-540-67690-2Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagisacompanyintheBertelsmannSpringerpublishinggroup. ©Springer-VerlagBerlinHeidelberg2000 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbySteingräberSatztechnikGmbH,Heidelberg Printedonacid-freepaper SPIN:10722125 06/3142 543210 Preface ThepapersinthisvolumewerepresentedatSWAT2000,theSeventhScandina- vianWorkshoponAlgorithmTheory.Theworkshop,whichisreallyaconference, has been held biennially since 1988, rotating between the (cid:12)ve Nordic countries (Sweden, Norway, Finland, Denmark, and Iceland). It also has a loose associa- tionwiththeWADS(WorkshoponAlgorithmsandDataStructures)conference thatisheldinoddnumberedyears.SWATisintendedasaforumforresearchers intheareaofdesignandanalysisofalgorithms.TheSWATconferencesarecoor- dinatedbytheSWATsteeringcommittee,whichconsistsofB.Aspvall(Bergen), S.Carlsson(Lule(cid:23)a),H.Hafsteinsson(U.Iceland),R.Karlsson(Lund),A.Lingas (Lund), E. Schmidt (Aarhus), and E. Ukkonen (Helsinki). The call for papers sought contributions in all areas of algorithms and data structures, including computational geometry, parallel and distributed comput- ing, graph theory, and computational biology. A total of 105 papers were sub- mitted, out of which the program committee selected 43 for presentation. In addition, invited lectures were presented by Uriel Feige (Weizmann), Mikkel Thorup (AT&T Labs-Research), and Esko Ukkonen (Helsinki). SWAT2000washeldinBergen,July5-7,2000,andwaslocallyorganizedby a committee consisting of Pinar Heggernes, Petter Kristiansen, Fredrik Manne, and Jan Arne Telle (chair), all from the department of informatics, University of Bergen. We wish to thank all the referees who aided in evaluating the papers. We also thank The Research Council of Norway (NFR) and the City of Bergen for (cid:12)nancial support. July 2000 Magnu(cid:19)s M. Halldo(cid:19)rsson VI Organization Program Committee Amotz Bar-Noy, Tel-Aviv Univ. Luisa Gargano, Univ. of Salerno Jens Gustedt, LORIA and INRIA Lorraine Magnu(cid:19)s M. Halldo(cid:19)rsson, chair, U. Iceland and U. Bergen Kazuo Iwama, Kyoto Univ. Klaus Jansen, Univ. of Kiel Jan Kratochv(cid:19)(cid:16)l, Charles Univ. Andrzej Lingas, Lund Univ. Jaikumar Radhakrishnan, Tata Institute R. Ravi, Carnegie Mellon Univ. Jo¨rg-Rudicher Sack, Carleton Univ. Baruch Schieber, IBM Research Sven Skyum, Univ. of Aarhus Hisao Tamaki, Meiji Univ. Jan Arne Telle, Univ. of Bergen Esko Ukkonen, Univ. of Helsinki Gerhard Woeginger, Technical Univ. Graz Referees Pankaj Agarwal Laura Grigori Jiri Matou(cid:20)sek Helmut Alt Joachim Gudmundsson Peter Bro Miltersen Larse Arge Bjarni V. Halldo(cid:19)rsson Gabriele Neyer David Avis Mikael Hammar Anna O¨stlin Luitpold Babel Michael Houle Rasmus Pagh Bruno Beauquier David Hutchinson Jakob Pagter Binay Bhattacharya Rahul Jain Christian N. S. Pedersen Therese Biedl Jesper Jansson Marco Pellegrini Andreas Bj¨orklund Rolf Karlsson Cecilia M. Procopiuc Claudson Bornstein T. Kavita Wojtek Rytter Gerth St(cid:28)lting Brodal Jyrki Kivinen Fatma Sibel Salman Eranda C(cid:24)ela Rolf Klein Sven Schuierer Timothy M. Chan Bettina Klinz Eike Seidel Joseph Cheriyan Jochen K¨onemann Pranab Sen Johanne Cohen Goran Konjevod Jop Sibeyn Artur Czumaj S. Krishnan Michiel Smid Frank Dehne Christos Levcopoulos Edyta Szymanska Ingvar Eidhammer Moshe Lewenstein Ariel Tamir Aleksei V. Fishkin Alex Lopez-Ortiz Santosh Vempala E(cid:19)ric Fleury Ross McConnell S. Venkatesh Fedor Fomin Ewa Malesinska Alexander Wol(cid:11) Gudmund S. Frandsen Monaldo Mastrolilli Anders Yeo Leszek Ga(cid:24)sieniec Brian M. Mayoh Table of Contents Invited Talks Dynamic Graph Algorithms with Applications......................... 1 Mikkel Thorup (AT&T Labs-Research) and David R. Karger (MIT) Coping with the NP-Hardness of the Graph Bandwidth Problem......... 10 Uriel Feige (Weizmann Institute) Toward Complete Genome Data Mining in Computational Biology ....... 20 Esko Ukkonen (University of Helsinki) Data Structures A New Trade-Off for Deterministic Dictionaries........................ 22 Rasmus Pagh (University of Aarhus) Improved Upper Bounds for Pairing Heaps ............................ 32 John Iacono (Rutgers University) Maintaining Center and Median in Dynamic Trees ..................... 46 Stephen Alstrup, Jacob Holm (IT University of Copenhagen), and Mikkel Thorup (AT&T Labs–Research) Dynamic Planar Convex Hull with Optimal Query Time and O(logn·loglogn) Update Time.................................. 57 Gerth Stølting Brodal and Riko Jacob (University of Aarhus) Dynamic Partitions A Dynamic Algorithm for Maintaining Graph Partitions ................ 71 Lyudmil G. Aleksandrov (Bulgarian Academy of Sciences) and Hristo N. Djidjev (University of Warwick) Data Structures for Maintaining Set Partitions ........................ 83 Michael A. Bender, Saurabh Sethia, and Steven Skiena (SUNY Stony Brook) Graph Algorithms Fixed Parameter Algorithms for Planar Dominating Set and Related Problems .............................................. 97 Jochen Alber (Universit¨at Tu¨bingen), Hans L. Bodlaender (Utrecht University),HenningFernau,andRolfNiedermeier(Universita¨tTu¨bingen) VIII Embeddings of k-Connected Graphs of Pathwidth k .................... 111 Arvind Gupta (Simon Fraser University), Naomi Nishimura (University of Waterloo), Andrzej Proskurowski (University of Oregon), and Prabhakar Ragde (University of Waterloo) On Graph Powers for Leaf-Labeled Trees.............................. 125 Naomi Nishimura, Prabhakar Ragde (University of Waterloo), and Dimitrios M. Thilikos (Universitat Polit`ecnica de Catalunya) Recognizing Weakly Triangulated Graphs by Edge Separability .......... 139 Anne Berry, Jean-Paul Bordat (LIRMM, Montpellier) and Pinar Heggernes (University of Bergen) Online Algorithms Caching for Web Searching.......................................... 150 Bala Kalyanasundaram (Georgetown University), John Noga (Technical University of Graz), Kirk Pruhs (University of Pittsburgh), and Gerhard Woeginger (Technical University of Graz) On-Line Scheduling with Precedence Constraints....................... 164 Yossi Azar and Leah Epstein (Tel-Aviv University) Scheduling Jobs Before Shut-Down................................... 175 Vincenzo Liberatore (UMIACS) Resource Augmentation in Load Balancing ............................ 189 Yossi Azar, Leah Epstein (Tel-Aviv University), and Rob van Stee (Centre for Mathematics and Computer Science, CWI) Fair versus Unrestricted Bin Packing ................................. 200 Yossi Azar (Tel-Aviv University), Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen (University of Southern Denmark) Approximation Algorithms A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs....................................................... 214 Piotr Berman (Pennsylvania State University) Approximation Algorithms for the Label-CoverMAX and Red-Blue Set Cover Problems.................................................... 220 David Peleg (Weizmann Institute) Approximation Algorithms for Maximum Linear Arrangement ........... 231 Refael Hassin and Shlomi Rubinstein (Tel-Aviv University) IX Approximation Algorithms for Clustering to Minimize the Sum of Diameters ................................... 237 Srinivas R. Doddi, Madhav V. Marathe (Los Alamos National Laboratory), S. S. Ravi (SUNY Albany), David Scot Taylor (UCLA), and Peter Widmayer (ETH) Matchings Robust Matchings and Maximum Clustering .......................... 251 Refael Hassin and Shlomi Rubinstein (Tel-Aviv University) The Hospitals/Residents Problem with Ties .......................... 259 Robert W. Irving, David F. Manlove, and Sandy Scott (University of Glasgow) Network Design Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph .. 272 Yefim Dinitz (Ben-Gurion University) and Ronit Nossenson (Technion) On the Minimum Augmentation of an (cid:7)-Connected Graph to a k-Connected Graph ............................................ 286 Toshimasa Ishii and Hiroshi Nagamochi (Toyohashi University of Technology) Locating Sources to Meet Flow Demands in Undirected Networks ........ 300 Kouji Arata (Osaka University), Satoru Iwata (University of Tokyo), Kazuhisa Makino, and Satoru Fujishige (Osaka University) Improved Greedy Algorithms for Constructing Sparse Geometric Spanners 314 Joachim Gudmundsson, Christos Levcopoulos (Lund University), and Giri Narasimhan (University of Memphis) Computational Geometry Computing the Penetration Depth of Two Convex Polytopes in 3D....... 328 Pankaj K. Agarwal (Duke University), Leonidas J. Guibas (Stanford University),SarielHar-Peled(DukeUniversity),AlexanderRabinovitch (Synopsys Inc.), and Micha Sharir (Tel Aviv University) Compact Voronoi Diagrams for Moving Convex Polygons ............... 339 Leonidas J. Guibas (Stanford University), Jack Snoeyink (University of North Carolina), and Li Zhang (Stanford University) Efficient Expected-Case Algorithms for Planar Point Location ........... 353 Sunil Arya, Siu-Wing Cheng (Hong Kong University of Science and Technology),DavidM.Mount(UniversityofMaryland),andH.Ramesh (Indian Institute of Science)