SWAT 2016 June 22-24, 2016 - Reykjavik, Iceland

15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)



Rasmus Pagh (Ed.)
ISBN 978-3-95977-011-8, LIPICS Vol. 53 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 14 MB)
Search Publication Server

Authors
  • Ahn, Hee-Kap
  • Amani, Mahdi
  • Aronov, Boris
  • Banerjee, Indranil
  • Banik, Aritra
  • Ben Basat, Ran
  • Bhattacharya, Binay
  • Biniaz, Ahmad
  • Björklund, Andreas
  • Bose, Prosenjit
  • Boyar, Joan
  • Byrka, Jaroslaw
  • Chan, Timothy M.
  • Chuzhoy, Julia
  • Cygan, Marek
  • Dabrowski, Konrad K.
  • Das, Sandip
  • De Carufel, Jean-Lou
  • Dross, François
  • Eidenbenz, Stephan J.
  • Einziger, Gil
  • Ene, Alina
  • Eppstein, David
  • Favrholdt, Lene M.
  • Friedman, Roy
  • Friggstad, Zachary
  • Ganguly, Arnab
  • Gawrychowski, Pawel
  • Golovach, Petr A.
  • Grimm, Carsten
  • Gupta, Sushmita
  • Hon, Wing-Kai
  • Iwama, Kazuo
  • Jansen, Klaus
  • Jan van Leeuwen, Erik
  • Kameda, Tsunehiko
  • Kanj, Iyad
  • Karczmarz, Adam
  • Kassner, Yaron
  • Kim Thang, Nguyen
  • Kolman, Petr
  • Komusiewicz, Christian
  • Könemann, Jochen
  • Korman, Matias
  • Kotrbcik, Michal
  • Koutecký, Martin
  • Kratsch, Dieter
  • Kübel, David
  • Land, Kati
  • Langetepe, Elmar
  • Larsen, Kim S.
  • Lewandowski, Mateusz
  • Lokshtanov, Daniel
  • Maack, Marten
  • Maheshwari, Anil
  • Marx, Dániel
  • Miyazaki, Shuichi
  • Mnich, Matthias
  • Moldenhauer, Carsten
  • Oh, Eunjin
  • Pagh, Rasmus
  • Papadimitriou, Christos H.
  • Paulusma, Daniël
  • Pilipczuk, Marcin
  • Pilipczuk, Michal
  • Pratt, Simon
  • Rahmati, Zahed
  • Rezapour, Mohsen
  • Richards, Dana
  • Risteski, Andrej
  • Roeloffzen, Marcel
  • Rutter, Ignaz
  • Sack, Jörg-Rüdiger
  • Salavatipour, Mohammad R.
  • Saurabh, Saket
  • Scheffer, Christian
  • Schmidt, Jens M.
  • Shadravan, Mohammad
  • Shah, Rahul
  • Smid, Michiel
  • Song, Zhao
  • Son, Wanbin
  • Sorge, Manuel
  • Stewart, Anthony
  • Suomela, Jukka
  • Tiwary, Hans Raj
  • Uznanski, Przemyslaw
  • van Renssen, André
    		•

    		  
    Front Matter, Table of Contents, Preface, Program Committee, Subreviewers
    Authors: Pagh, Rasmus

    Abstract | Document (362 KB) | BibTeX

    Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding
    Authors: Friggstad, Zachary ; Rezapour, Mohsen ; Salavatipour, Mohammad R.

    Abstract | Document (530 KB) | BibTeX

    Approximation Algorithms for Node-Weighted Prize-Collecting Steiner Tree Problems on Planar Graphs
    Authors: Byrka, Jaroslaw ; Lewandowski, Mateusz ; Moldenhauer, Carsten

    Abstract | Document (530 KB) | BibTeX

    A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
    Authors: Friggstad, Zachary ; Könemann, Jochen ; Shadravan, Mohammad

    Abstract | Document (507 KB) | BibTeX

    A Linear Kernel for Finding Square Roots of Almost Planar Graphs
    Authors: Golovach, Petr A. ; Kratsch, Dieter ; Paulusma, Daniël ; Stewart, Anthony

    Abstract | Document (513 KB) | BibTeX

    Linear-Time Recognition of Map Graphs with Outerplanar Witness
    Authors: Mnich, Matthias ; Rutter, Ignaz ; Schmidt, Jens M.

    Abstract | Document (527 KB) | BibTeX

    The p-Center Problem in Tree Networks Revisited
    Authors: Banik, Aritra ; Bhattacharya, Binay ; Das, Sandip ; Kameda, Tsunehiko ; Song, Zhao

    Abstract | Document (626 KB) | BibTeX

    A Simple Mergeable Dictionary
    Authors: Karczmarz, Adam

    Abstract | Document (503 KB) | BibTeX

    Cuckoo Filter: Simplification and Analysis
    Authors: Eppstein, David

    Abstract | Document (476 KB) | BibTeX

    Randomized Algorithms for Finding a Majority Element
    Authors: Gawrychowski, Pawel ; Suomela, Jukka ; Uznanski, Przemyslaw

    Abstract | Document (467 KB) | BibTeX

    A Framework for Dynamic Parameterized Dictionary Matching
    Authors: Ganguly, Arnab ; Hon, Wing-Kai ; Shah, Rahul

    Abstract | Document (511 KB) | BibTeX

    Efficient Summing over Sliding Windows
    Authors: Ben Basat, Ran ; Einziger, Gil ; Friedman, Roy ; Kassner, Yaron

    Abstract | Document (567 KB) | BibTeX

    Lower Bounds for Approximation Schemes for Closest String
    Authors: Cygan, Marek ; Lokshtanov, Daniel ; Pilipczuk, Marcin ; Pilipczuk, Michal ; Saurabh, Saket

    Abstract | Document (482 KB) | BibTeX

    Coloring Graphs Having Few Colorings Over Path Decompositions
    Authors: Björklund, Andreas

    Abstract | Document (441 KB) | BibTeX

    Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
    Authors: Kanj, Iyad ; Komusiewicz, Christian ; Sorge, Manuel ; Jan van Leeuwen, Erik

    Abstract | Document (460 KB) | BibTeX

    On Routing Disjoint Paths in Bounded Treewidth Graphs
    Authors: Ene, Alina ; Mnich, Matthias ; Pilipczuk, Marcin ; Risteski, Andrej

    Abstract | Document (599 KB) | BibTeX

    Colouring Diamond-free Graphs
    Authors: Dabrowski, Konrad K. ; Dross, François ; Paulusma, Daniël

    Abstract | Document (483 KB) | BibTeX

    Below All Subsets for Some Permutational Counting Problems
    Authors: Björklund, Andreas

    Abstract | Document (435 KB) | BibTeX

    Extension Complexity, MSO Logic, and Treewidth
    Authors: Kolman, Petr ; Koutecký, Martin ; Tiwary, Hans Raj

    Abstract | Document (508 KB) | BibTeX

    Optimal Online Escape Path Against a Certificate
    Authors: Langetepe, Elmar ; Kübel, David

    Abstract | Document (630 KB) | BibTeX

    Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling
    Authors: Kim Thang, Nguyen

    Abstract | Document (405 KB) | BibTeX

    Online Dominating Set
    Authors: Boyar, Joan ; Eidenbenz, Stephan J. ; Favrholdt, Lene M. ; Kotrbcik, Michal ; Larsen, Kim S.

    Abstract | Document (480 KB) | BibTeX

    Sorting Under Forbidden Comparisons
    Authors: Banerjee, Indranil ; Richards, Dana

    Abstract | Document (570 KB) | BibTeX

    Total Stability in Stable Matching Games
    Authors: Gupta, Sushmita ; Iwama, Kazuo ; Miyazaki, Shuichi

    Abstract | Document (489 KB) | BibTeX

    Estimating The Makespan of The Two-Valued Restricted Assignment Problem
    Authors: Jansen, Klaus ; Land, Kati ; Maack, Marten

    Abstract | Document (566 KB) | BibTeX

    A Plane 1.88-Spanner for Points in Convex Position
    Authors: Amani, Mahdi ; Biniaz, Ahmad ; Bose, Prosenjit ; De Carufel, Jean-Lou ; Maheshwari, Anil ; Smid, Michiel

    Abstract | Document (644 KB) | BibTeX

    Approximating the Integral Fréchet Distance
    Authors: Maheshwari, Anil ; Sack, Jörg-Rüdiger ; Scheffer, Christian

    Abstract | Document (676 KB) | BibTeX

    Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts
    Authors: De Carufel, Jean-Lou ; Grimm, Carsten ; Maheshwari, Anil ; Smid, Michiel

    Abstract | Document (772 KB) | BibTeX

    A Clustering-Based Approach to Kinetic Closest Pair
    Authors: Chan, Timothy M. ; Rahmati, Zahed

    Abstract | Document (563 KB) | BibTeX

    Constrained Geodesic Centers of a Simple Polygon
    Authors: Oh, Eunjin ; Son, Wanbin ; Ahn, Hee-Kap

    Abstract | Document (532 KB) | BibTeX

    Time-Space Trade-offs for Triangulating a Simple Polygon
    Authors: Aronov, Boris ; Korman, Matias ; Pratt, Simon ; van Renssen, André ; Roeloffzen, Marcel

    Abstract | Document (556 KB) | BibTeX

    Excluded Grid Theorem: Improved and Simplified (Invited Talk)
    Authors: Chuzhoy, Julia

    Abstract | Document (207 KB) | BibTeX

    The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk)
    Authors: Marx, Dániel

    Abstract | Document (240 KB) | BibTeX

    Computation as a Scientific Weltanschauung (Invited Talk)
    Authors: Papadimitriou, Christos H.

    Abstract | Document (216 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI