LEADER 06657nam 22008055 450 001 9910484732303321 005 20251226202906.0 010 $a3-540-69903-1 024 7 $a10.1007/978-3-540-69903-3 035 $a(CKB)1000000000490271 035 $a(SSID)ssj0000355433 035 $a(PQKBManifestationID)11272646 035 $a(PQKBTitleCode)TC0000355433 035 $a(PQKBWorkID)10319705 035 $a(PQKB)10841078 035 $a(DE-He213)978-3-540-69903-3 035 $a(MiAaPQ)EBC3068697 035 $a(PPN)127054782 035 $a(BIP)23280929 035 $a(EXLCZ)991000000000490271 100 $a20100301d2008 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithm Theory ? SWAT 2008 $e11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008, Proceedings /$fedited by Joachim Gudmundsson 205 $a1st ed. 2008. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2008. 215 $a1 online resource (XIII, 438 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5124 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-540-69900-7 320 $aIncludes bibliographical references and index. 327 $aInvited Lectures -- A Survey of Results for Deletion Channels and Related Synchronization Channels -- Nash Bargaining Via Flexible Budget Markets -- Contributed Papers -- Simplified Planar Coresets for Data Streams -- Uniquely Represented Data Structures for Computational Geometry -- I/O Efficient Dynamic Data Structures for Longest Prefix Queries -- Guarding Art Galleries: The Extra Cost for Sculptures Is Linear -- Vision-Based Pursuit-Evasion in a Grid -- Angle Optimization in Target Tracking -- Improved Bounds for Wireless Localization -- Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem -- Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint -- The Maximum Energy-Constrained Dynamic Flow Problem -- Bounded Unpopularity Matchings -- Data Structures with Local Update Operations -- On the Redundancy of Succinct Data Structures -- Confluently Persistent Tries for Efficient Version Control -- A Uniform Approach Towards Succinct Representation of Trees -- An Algorithm for L(2,1)-Labeling of Trees -- Batch Coloring Flat Graphs and Thin -- Approximating the Interval Constrained Coloring Problem -- A Path Cover Technique for LCAs in Dags -- Boundary Labeling with Octilinear Leaders -- Distributed Disaster Disclosure -- Reoptimization of Steiner Trees -- On the Locality of Extracting a 2-Manifold in -- On Metric Clustering to Minimize the Sum of Radii -- On Covering Problems of Rado -- Packing Rectangles into 2OPT Bins Using Rotations -- A Preemptive Algorithm for Maximizing Disjoint Paths on Trees -- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs -- On a Special Co-cycle Basis of Graphs -- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs -- Spanners of Additively Weighted Point Sets -- The Kinetic Facility Location Problem -- Computing the Greedy Spanner in Near-Quadratic Time -- Parameterized Computational Complexity of Dodgson and Young Elections -- Online Compression Caching -- On Trade-Offs in External-Memory Diameter-Approximation. 330 $aThe Scandinavian Workshop on Algorithm Theory (SWAT) is a biennial int- national conferenceintended as a forum for researchersin the area of design and analysisofalgorithmsanddatastructures. The'rstSWATworkshopwasheldin Halmstad, Sweden, in 1988. Since then it has been held biennially, rotating - tween the ?ve Nordic countries - Denmark, Finland, Iceland, Norway and S- 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 Sc- 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 original research on algorithms and data structures in all areas, including but not limited to: approximation algorithms, compu- tionalbiology,computationalgeometry,distributedalgorithms,external-memory algorithms,graphalgorithms,online algorithms,optimization algorithms,par- 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,andevaluatedonthequ- ity,originalityandrelevanceto the symposium. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5124 606 $aArtificial intelligence$xData processing 606 $aDiscrete mathematics 606 $aAlgorithms 606 $aComputer networks 606 $aComputer science$xMathematics 606 $aComputer graphics 606 $aData Science 606 $aDiscrete Mathematics 606 $aAlgorithms 606 $aComputer Communication Networks 606 $aDiscrete Mathematics in Computer Science 606 $aComputer Graphics 615 0$aArtificial intelligence$xData processing. 615 0$aDiscrete mathematics. 615 0$aAlgorithms. 615 0$aComputer networks. 615 0$aComputer science$xMathematics. 615 0$aComputer graphics. 615 14$aData Science. 615 24$aDiscrete Mathematics. 615 24$aAlgorithms. 615 24$aComputer Communication Networks. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aComputer Graphics. 676 $a005.73 701 $aGudmundsson$b Joachim$01750518 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484732303321 996 $aAlgorithm theory-- SWAT 2008$94185161 997 $aUNINA