Algorithm Theory - SWAT 2014
14th Scandinavian Symposium and Workshops, SWAT 2014, Copenhagen, Denmark, July 2-4, 2014. ProceedingsR. Ravi, Inge Li Gortz (Eds.)
This book constitutes the refereed proceedings of the 14th International Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014, held in Copenhagen, Denmark, in July 2014. The 33 papers were carefully reviewed and selected from a total of 134 submissions. The papers present original research and cover a wide range of topics in the field of design and analysis of algorithms and data structures including but not limited to approximation algorithms, parameterized algorithms, computational biology, computational geometry and topology, distributed algorithms, external-memory algorithms, exponential algorithms, graph algorithms, online algorithms, optimization algorithms, randomized algorithms, streaming algorithms, string algorithms, sublinear algorithms and algorithmic game theory.
Table of Contents
I/O-Efficient Range Minima Queries - Peyman Afshani and Nodari Sitchinava 1
Online Makespan Minimization with Parallel Schedules - Susanne Albers and Matthias Hellwig 13
Expected Linear Time Sorting for Word Size O (log 2 n log log n ) - Djamal Belazzougui, Gerth Stølting Brodal, and Jesper Sindahl Nielsen 26
Amortized Analysis of Smooth Quadtrees in All Dimensions - Huck Bennett and Chee Yap 38
New Approximability Results for the Robust k -Median Problem - Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann 50
Trees and Co-trees with Bounded Degrees in Planar 3-connected Graphs - Therese Biedl 62
Approximating the Revenue Maximization Problem with Sharp Demands - Vittorio Bilò, Michele Flammini, and Gianpiero Monaco 74
Reconfiguring Independent Sets in Claw-Free Graphs - Paul Bonsma, Marcin Kaminski, and Marcin Wrochna 86
Competitive Online Routing on Delaunay Triangulations - Prosenjit Bose, Jean-Lou De Carufel, Stephane Durocher, and Perouz Taslakian 98
Optimal Planar Orthogonal Skyline Counting Queries - Gerth Stølting Brodal and Kasper Green Larsen 110
B-slack Trees: Space Efficient B-Trees - Trevor Brown 122
Approximately Minwise Independence with Twisted Tabulation - Søren Dahlgaard and Mikkel Thorup 134
Separability of Imprecise Points - Mark de Berg, Ali D. Mehrabi, and Farnaz Sheikhi 146
Line-Distortion, Bandwidth and Path-Length of a Graph - Feodor F. Dragan, Ekkehard Köhler, and Arne Leitert 158
Colorful Bin Packing - György Dósa and Leah Epstein 170
Algorithms Parameterized by Vertex Cover and Modular Width, through Potential Maximal Cliques - Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, and Ioan Todinca 182
Win-Win Kernelization for Degree Sequence Completion Problems- Vincent Froese, André Nichterlein, and Rolf Niedermeier 194
On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem - Toshihiro Fujito 206
Covering Problems in Edge- and Node-Weighted Graphs - Takuro Fukunaga 217
Colored Range Searching in Linear Space - Roberto Grossi and Søren Vind 229
Fast Dynamic Graph Algorithms for Parameterized Problems - Yoichi Iwata and Keigo Oka 241
Extending Partial Representations of Proper and Unit Interval Graphs - Pavel Klavik, Jan Kratochvil, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, and TomásVyskocil 253
Minimum Tree Supports for Hypergraphs and Low-Concurrency Euler Diagrams - Boris Klemz, Tamara Mchedlidze, and Martin Nöllenburg 265
Additive Spanners: A Simple Construction - Mathias Bæk Tejs Knudsen 277
Assigning Channels via the Meet-in-the-Middle Approach - Lukasz Kowalik and Arkadiusz Socala 282
Consistent Subset Sampling - Konstantin Kutzkov and Rasmus Pagh 294
Triangle Counting in Dynamic Graph Streams - Konstantin Kutzkov and Rasmus Pagh 306
Linear Time LexDFS on Cocomparability Graphs - Ekkehard Köhler and Lalla Mouatadid 319
Quantum Algorithms for Matrix Products over Semirings - Francois Le Gall and Harumichi Nishimura 331
Ranked Document Selection - J. Ian Munro, Gonzalo Navarro, Rahul Shah, and Sharma V. Thankachan 334
Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments - Anup Joshi and N.S. Narayanaswamy 357
Reduction Techniques for Graph Isomorphism in the Context of Width Parameters - Yota Otachi and Pascal Schweitzer 368
Approximate Counting of Matchings in (3,3)-Hypergraphs- Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, and Edyta Szymanska 380
Author Index 393
Springer, Lecture Notes in Computer Science - Volume 8503, Paperback, english, 394 pages
