Lecture Notes in Computer Science 5124 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Joachim Gudmundsson (Ed.) Algorithm Theory – SWAT 2008 11th Scandinavian Workshop onAlgorithm Theory Gothenburg, Sweden, July 2-4, 2008 Proceedings 1 3 VolumeEditor JoachimGudmundsson NICTA LockedBag9013 AlexandriaNSW1435,Australia E-mail:[email protected] LibraryofCongressControlNumber:Appliedfor CRSubjectClassification(1998):F.2,E.1,G.2,I.3.5,C.2 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-69900-7SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-69900-2SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2008 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:12321810 06/3180 543210 Preface The Scandinavian Workshop on Algorithm Theory (SWAT) is a biennial inter- nationalconferenceintendedasaforumforresearchersintheareaofdesignand analysisofalgorithmsanddatastructures.ThefirstSWATworkshopwasheldin Halmstad, Sweden, in 1988. Since then it has been held biennially, rotating be- tween the five Nordic countries – Denmark, Finland, Iceland, Norway and Swe- den, with the exception of 2006 when it was in Riga. Earlier SWATs were held in Humlebæk, Denmark (2004),Turku,Finland (2002),Bergen,Norway(2000), Stockholm, Sweden (1998), Reykjavik, Iceland (1996), ˚Arhus, Denmark (1994), Helsinki,Finland(1992),Bergen,Norway(1990)andHalmstad,Sweden(1988). This volume contains the contributed papers presented at the 11th Scan- dinavian Workshop on Algorithm Theory (SWAT 2008), held in Gothenburg, Sweden, July 2–4, 2008. In addition, the volume also includes abstracts of an invited talk by Michael Mitzenmacher on “A Survey of Results for Deletion Channels and Related Synchronization Channels”and by Vijay V. Vazirani on “Nash Bargaining via Flexible Budget Markets.” Papers were solicited for originalresearchon algorithms and data structures in all areas, including but not limited to: approximation algorithms, computa- tionalbiology,computationalgeometry,distributedalgorithms,external-memory algorithms,graphalgorithms,onlinealgorithms,optimizationalgorithms,paral- lel algorithms, randomized algorithms, string algorithms and algorithmic game theory. The 36 contributed papers were chosen from 111 submissions. Revised and expanded versions of selected papers will be considered for publication in a special issue of Algorithmica. The best paper award was given to Yossi Azar, Uriel Feige and Daniel Glasner for their paper “A Preemptive Algorithm for Maximizing Disjoint Paths on Trees.” Eachpaperwasreviewedbyatleastthreereferees,andevaluatedonthequal- ity,originalityandrelevancetothesymposium.Thechallengingtaskofselecting thepapersforpresentationwasperformedbythemembersofourProgramCom- mittee and external reviewers.All of them deserve special thanks for their hard work. Wethankallofthosewhosubmittedpapersforcontributingtoaninteresting and diverse conference. April 2008 Joachim Gudmundsson Organization Program Chair Joachim Gudmundsson, NICTA, Australia Program Committee Mark de Berg, TU Eindhoven, The Netherlands Michael Elkin, Ben-Gurion University, Israel Leah Epstein, University of Haifa, Israel Fedor Fomin, University of Bergen, Norway Leszek Gasieniec, University of Liverpool, UK (cid:2) Anupam Gupta, Carnegie Mellon University, USA Thore Husfeldt, Lund University, Sweden Johan H˚astad, Royal Institute of Technology,Sweden Nicole Immorlica, Centrum voor Wiskunde en Informatica, The Netherlands Mikko Koivisto, HIIT, University of Helsinki, Finland Peter Bro Miltersen, University of Aarhus, Denmark Pat Morin, Carleton University, Canada Rasmus Pagh,IT University of Copenhagen, Denmark Marina Papatriantafilou,Chalmers University of Technology,Sweden Mihai Paˇtra¸scu, MIT, USA Kunihiko Sadakane, Kyushu University, Japan Martin Skutella, TU Berlin, Germany Christian Sohler, University of Paderborn,Germany Local Organization Ewa Cederheim-W¨aingelin Rebecca Cyr´en Georgios Georgiadis Catharina Jerkbrant Marina Papatriantafilou Tiina Rankanen Philippas Tsigas Steering Committee Lars Arge, University of Aarhus, Denmark Magnu´s M. Halldo´rsson, University of Iceland, Iceland Rolf Karlsson, Lund University, Sweden Andrzej Lingas, Lund University, Sweden Jan Arne Telle, University of Bergen, Norway Esko Ukkonen, University of Helsinki, Finland VIII Organization Sponsoring Institutions Security Arena Lindholmen Science Park External Reviewers Marcel R. Ackermann Janka Chleb´ıkova´ Anders Gidenstam Dror Aiger Marek Chrobak Inge Li Gørtz Mohammad Ali Abam S´ebastien Collette Peter Golovach Nina Amenta Derek Corneil Lee-Ad Gottlieb Daniel Andersson Annalisa DeBonis Phuong Ha Sunil Arya Brian Dean Mikael Hammar Hideo Bannai Bastian Degener Sariel Har-Peled Amitabh Basu Kedar Dhamdhere Refael Hassin Boaz Ben-Moshe Karim Dou¨ıeb Herman Haverkort Michael Bender Vida Dujmovi´c Meng He Marcin Bienkowski Lene M. Favrholdt Stefan Hougardy Philip Bille Fernando Mario Oliveira John Iacono Vincenzo Bonifaci Filho Csan´ad Imreh Peter Braß Sorelle Friedler Klaus Jansen Kevin Buchin Zhang Fu Jesper Jansson Maike Buchin Naveen Garg Juha Karkkainen Jaroslaw Byrka Serge Gaspers Petteri Kaski Daniel Cederman Giorgos Georgiadis Hyosil Kim Organization IX Ralf Klasing Shuichi Miyazaki Elad Michael Schiller Rolf Klein Morteza Monemizadeh Jiˇr´ı Sgall Boris Koldehofe Haiko Mu¨ller Anastasios Sidiropoulos Guy Kortsarz Viswanath Nagarajan Shakhar Smorodinsky Mirosl(cid:2)aw Korzeniowski Alfredo Navarra Bettina Speckmann Marc van Kreveld Bengt Nilsson Rob van Stee Danny Krizanc Zeev Nutov Jukka Suomela Alexander Kr¨oller Joseph O’Rourke Maxim Sviridenko Sven O. Krumke Hirotaka Ono Xuehou Tan Marcin Kubica Aris Pagourtzis Orestis Telelis Jochen K¨onemann Seth Pettie Peter Tiedemann Christiane Lammersen Igor Potapov Laura Toma Stefan Langerman David Pritchard Ryuhei Uehara Erik Jan van Leeuwen Artem Pyatkin Taso Viglas Asaf Levin Vijaya Ramachandran Antoine Vigneron Christian Liebchen R. Ravi Yngve Villanger Andrzej Lingas Dror Rawitz Berthold V¨ocking Tam´as Lukovszki Daniel Reichman Renato Werneck Anil Maheshwari Romeo Rizzi Alexander Wolff Hamid Mahini Genevi`eve Roberge Thomas Wolle Azarakhsh Malekian Liam Roditty Maverick Woo Nunkesser Marc Aaron Roth Koichi Yamazaki Da´niel Marx Milan Ruˇzi´c Norbert Zeh Daniel Meister Harald R¨acke Pawe(cid:2)l Z˙ylin´ski George Mertzios Peter Sanders Julian Mestre Saket Saurabh Table of Contents Invited Lectures ASurveyofResults forDeletionChannelsandRelatedSynchronization Channels ....................................................... 1 Michael Mitzenmacher Nash Bargaining Via Flexible Budget Markets (Abstract) ............. 4 Vijay V. Vazirani Contributed Papers Simplified Planar Coresets for Data Streams......................... 5 John Hershberger and Subhash Suri Uniquely Represented Data Structures for Computational Geometry.... 17 Guy E. Blelloch, Daniel Golovin, and Virginia Vassilevska I/O Efficient Dynamic Data Structures for Longest Prefix Queries...... 29 Moshe Hershcovitch and Haim Kaplan Guarding Art Galleries: The Extra Cost for Sculptures Is Linear ....... 41 Louigi Addario-Berry, Omid Amini, Jean-S´ebastien Sereni, and St´ephan Thomass´e Vision-Based Pursuit-Evasionin a Grid............................. 53 Adrian Dumitrescu, Howi Kok, Ichiro Suzuki, and Pawel(cid:2) Z˙ylin´ski Angle Optimization in Target Tracking ............................. 65 Beat Gfeller, Matu´ˇs Mihala´k, Subhash Suri, Elias Vicari, and Peter Widmayer Improved Bounds for Wireless Localization.......................... 77 Tobias Christ, Michael Hoffmann, Yoshio Okamoto, and Takeaki Uno Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem ........................................................ 90 Yuval Rabani and Gabriel Scalosub Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint ...................................................... 102 Hans L. Bodlaender, Richard B. Tan, Thomas C. van Dijk, and Jan van Leeuwen XII Table of Contents The Maximum Energy-ConstrainedDynamic Flow Problem ........... 114 S´andor P. Fekete, Alexander Hall, Ekkehard K¨ohler, and Alexander Kro¨ller Bounded Unpopularity Matchings.................................. 127 Chien-Chung Huang, Telikepalli Kavitha, Dimitrios Michail, and Meghana Nasre Data Structures with Local Update Operations ...................... 138 Yakov Nekrich On the Redundancy of Succinct Data Structures ..................... 148 Alexander Golynski, Rajeev Raman, and S. Srinivasa Rao Confluently Persistent Tries for Efficient Version Control.............. 160 Erik D. Demaine, Stefan Langerman, and Eric Price A Uniform Approach Towards Succinct Representation of Trees........ 173 Arash Farzan and J. Ian Munro An O(n1.75) Algorithm for L(2,1)-Labeling of Trees .................. 185 Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, and Yushi Uno Batch Coloring Flat Graphs and Thin .............................. 198 Magnu´s M. Halldo´rsson and Hadas Shachnai Approximating the Interval Constrained Coloring Problem ............ 210 Ernst Althaus, Stefan Canzar, Khaled Elbassioni, Andreas Karrenbauer, and Julia´n Mestre A Path Cover Technique for LCAs in Dags.......................... 222 Mirosl(cid:2)aw Kowaluk, Andrzej Lingas, and Johannes Nowak Boundary Labeling with Octilinear Leaders ......................... 234 Michael A. Bekos, Micheal Kaufmann, Martin No¨llenburg, and Antonios Symvonis Distributed Disaster Disclosure .................................... 246 Bernard Mans, Stefan Schmid, and Roger Wattenhofer Reoptimization of Steiner Trees.................................... 258 Davide Bilo`, Hans-Joachim B¨ockenhauer, Juraj Hromkoviˇc, Richard Kr´aloviˇc, Tobias Mo¨mke, Peter Widmayer, and Anna Zych On the Locality of Extracting a 2-Manifold in IR3 .................... 270 Daniel Dumitriu, Stefan Funke, Martin Kutz, and Nikola Milosavljevi´c On Metric Clustering to Minimize the Sum of Radii .................. 282 Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan