SWAT 2016

Accepted Papers

• On Routing Disjoint Paths in Bounded Treewidth Graphs
  Alina Ene, Matthias Mnich, Marcin Pilipczuk and Andrej Risteski
• A Clustering-Based Approach to Kinetic Closest Pair
  Timothy M. Chan and Zahed Rahmati
• Linear-Time Recognition of Map Graphs with Outerplanar Witness
  Matthias Mnich, Ignaz Rutter and Jens M. Schmidt
• Sorting Under Forbidden Comparisons
  Indranil Banerjee and Dana Richards
• Time-Space Trade-offs for Triangulating a Simple Polygon
  Boris Aronov, Simon Pratt, Matias Korman, André van Renssen and Marcel Roeloffzen
• A Linear Kernel for Finding Square Roots of Almost Planar Graphs
  Petr Golovach, Dieter Kratsch, Daniel Paulusma and Anthony Stewart
• A Plane 1.88-Spanner for Points in Convex Position
  Ahmad Biniaz, Anil Maheshwari, Michiel Smid, Prosenjit Bose, Mahdi Amani and Jean-Lou De Carufel
• A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
  Zachary Friggstad, Jochen Koenemann and Mohammad Shadravan
• Colouring Diamond-free Graphs
  Konrad Kazimierz Dabrowski, François Dross and Daniel Paulusma
• Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding
  Zachary Friggstad, Mohsen Rezapour and Mohammad Salavatipour
• Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts
  Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari and Michiel Smid
• Approximating the Integral Fréchet Distance
  Christian Scheffer, Jorg Sack and Anil Maheshwari
• Total Stability in Stable Matching Games
  Sushmita Gupta, Kazuo Iwama and Shuichi Miyazaki
• A Simple Mergeable Dictionary
  Adam Karczmarz
• Extension Complexity, MSO Logic, and Treewidth
  Petr Kolman, Martin Koutecky and Hans Raj Tiwary
• Cuckoo Filter: Simplification and Analysis
  David Eppstein
• Efficient Summing over Sliding Windows
  Ran Ben Bassat, Gil Einziger, Roy Friedman and Yaron Kassner
• Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling
  Kim Thang Nguyen
• Below all subsets for some permutational counting problems
  Andreas Björklund
• Optimal online escape path against a certificate
  Elmar Langetepe and David Kübel
• Coloring Graphs having Few Colorings over Path Decompositions
  Andreas Björklund
• Online Dominating Set
  Joan Boyar, Stephan J. Eidenbenz, Lene Favrholdt, Michal Kotrbčík and Kim S. Larsen
• Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
  Iyad Kanj, Christian Komusiewicz, Manuel Sorge and Erik Jan van Leeuwen
• Estimating The Makespan of The Two-Valued Restricted Assignment Problem
  Klaus Jansen, Kati Land and Marten Maack
• A Framework for Dynamic Parameterized Dictionary Matching
  Arnab Ganguly, Wing-Kai Hon and Rahul Shah
• Constrained Geodesic Center of a Simple Polygon
  Eunjin Oh, Wanbin Son and Hee-Kap Ahn
• The p-Center Problem in Tree Networks Revisited
  Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda and Zhao Song
• Lower bounds for approximation schemes for Closest String
  Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh
• Randomized algorithms for finding a majority element
  Pawel Gawrychowski, Jukka Suomela and Przemysław Uznański
• Approximation algorithms for Node-weighted Prize-collecting Steiner Tree problems on planar graphs
  Mateusz Lewandowski, Jarosław Byrka and Carsten Moldenhauer