LEADER 07837nam 22008175 450 001 9910767529603321 005 20200629221617.0 010 $a3-540-27810-9 024 7 $a10.1007/b98413 035 $a(CKB)1000000000212447 035 $a(DE-He213)978-3-540-27810-8 035 $a(SSID)ssj0000101066 035 $a(PQKBManifestationID)11108836 035 $a(PQKBTitleCode)TC0000101066 035 $a(PQKBWorkID)10037368 035 $a(PQKB)10066096 035 $a(MiAaPQ)EBC3087237 035 $a(PPN)155217623 035 $a(EXLCZ)991000000000212447 100 $a20121227d2004 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aAlgorithm Theory - SWAT 2004 $e9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings /$fedited by Torben Hagerup, Jyrki Katajainen 205 $a1st ed. 2004. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2004. 215 $a1 online resource (XII, 512 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v3111 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-22339-8 320 $aIncludes bibliographical references at the end of each chapters and index. 327 $aInvited Contributions -- Design and Analysis of Dynamic Multithreaded Algorithms -- Cache-Oblivious Algorithms and Data Structures -- Refereed Contributions -- Getting the Best Response for Your Erg -- Auctions with Budget Constraints -- Tight Approximability Results for Test Set Problems in Bioinformatics -- Robust Subgraphs for Trees and Paths -- Collective Tree Spanners of Graphs -- Optimally Competitive List Batching -- The Relative Worst Order Ratio Applied to Seat Reservation -- Online Maintenance of k-Medians and k-Covers on a Line -- Matching Polyhedral Terrains Using Overlays of Envelopes -- Independent Set of Intersection Graphs of Convex Objects in 2D -- Maximizing the Area of Overlap of Two Unions of Disks Under Rigid Motion -- Construction of the Nearest Neighbor Embracing Graph of a Point Set -- Connectivity of Graphs Under Edge Flips -- Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity -- A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension -- Railway Delay Management: Exploring Its Algorithmic Complexity -- Layered Heaps -- Melding Priority Queues -- An Algorithm for Cyclic Edge Connectivity of Cubic Graphs -- Subexponential-Time Framework for Optimal Embeddings of Graphs in Integer Lattices -- New Algorithms for Enumerating All Maximal Cliques -- The Multi-multiway Cut Problem -- The Bottleneck Problem with Minimum Quantity Commitments -- All-Norm Approximation for Scheduling on Identical Machines -- Approximation Algorithms for the General Max-min Resource Sharing Problem: Faster and Simpler -- Approximation Schemes for the Crane Scheduling Problem -- Improved Approximation Algorithms for the Single-Sink Buy-at-Bulk Network Design Problems -- A ( )?Approximation Algorithm for the Stable Marriage Problem -- Maximizing the Number of Packed Rectangles -- Two Space Saving Tricks for Linear Time LCP Array Computation -- Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles -- Faster Deterministic Gossiping in Directed Ad Hoc Radio Networks -- Online Scheduling of Splittable Tasks in Peer-to-Peer Networks -- The Optimal Online Algorithms for Minimizing Maximum Lateness -- Power Assignment in Radio Networks with Two Power Levels -- Pointed Binary Encompassing Trees -- On Geometric Structure of Global Roundings for Graphs and Range Spaces -- External Connected Components -- Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths -- Simplified External Memory Algorithms for Planar DAGs. 330 $aThis volume contains the papers presented at SWAT 2004, the 9th Scandi- vian Workshop on Algorithm Theory, which was held on July 8?10, 2004, at the Louisiana Museum of Modern Art in Humlebæk on the Øresund coast north of Copenhagen. The SWAT workshop, in reality a full-?edged conference, has been held biennially since 1988 and rotates among the ?ve Nordic countries, D- mark, Finland, Iceland, Norway, and Sweden. The previous meetings took place ? in Halmstad (1988), Bergen (1990), Helsinki (1992), Arhus (1994), Reykjavik (1996), Stockholm (1998), Bergen (2000), and Turku (2002). SWAT alternates with the Workshop on Algorithms and Data Structures (WADS), held in o- numbered years. Thecallforpapersinvitedcontributionsonallaspectsofalgorithmtheory.A totalof121submissionswasreceived?anoverallSWAThigh.Theseunderwent thorough reviewing, and the program committee met in Copenhagen on March 20?21, 2004, and selected 40 papers for presentation at the conference. The programcommitteewasimpressedwiththequalityofthesubmissionsand,given the constraints imposed by the choice of conference venue and duration, had to make some tough decisions. The scienti?c program was enriched by invited presentations by Gerth Stølting Brodal (University of Aarhus) and Charles E. Leiserson (Massachusetts Institute of Technology). TwosatelliteeventswereheldimmediatelybeforeSWAT2004:theWorkshop on On-Line Algorithms (OLA 2004), organized by members of the Department of Mathematics and Computer Science at the University of Southern Denmark, and the Summer School on Experimental Algorithmics, organized by the Perf- mance Engineering Laboratory in the Department of Computing at the Univ- sity of Copenhagen. More information about SWAT 2004 and its satellite events is available at the conference web sitehttp://swat.diku.dk/. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v3111 606 $aNumerical analysis 606 $aMathematical models 606 $aAlgorithms 606 $aComputer communication systems 606 $aData structures (Computer science) 606 $aComputer science?Mathematics 606 $aNumerical Analysis$3https://scigraph.springernature.com/ontologies/product-market-codes/M14050 606 $aMathematical Modeling and Industrial Mathematics$3https://scigraph.springernature.com/ontologies/product-market-codes/M14068 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 606 $aComputer Communication Networks$3https://scigraph.springernature.com/ontologies/product-market-codes/I13022 606 $aData Structures$3https://scigraph.springernature.com/ontologies/product-market-codes/I15017 606 $aDiscrete Mathematics in Computer Science$3https://scigraph.springernature.com/ontologies/product-market-codes/I17028 615 0$aNumerical analysis. 615 0$aMathematical models. 615 0$aAlgorithms. 615 0$aComputer communication systems. 615 0$aData structures (Computer science). 615 0$aComputer science?Mathematics. 615 14$aNumerical Analysis. 615 24$aMathematical Modeling and Industrial Mathematics. 615 24$aAlgorithm Analysis and Problem Complexity. 615 24$aComputer Communication Networks. 615 24$aData Structures. 615 24$aDiscrete Mathematics in Computer Science. 676 $a518/.1 702 $aHagerup$b Torben$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aKatajainen$b Jyrki$4edt$4http://id.loc.gov/vocabulary/relators/edt 712 12$aScandinavian Workshop on Algorithm Theory 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910767529603321 996 $aAlgorithm Theory - SWAT 2004$92158509 997 $aUNINA