WADS 2015

14th International Symposium on

Algorithms and Data Structures

August 5-7, 2015

Victoria, Canada

Schedule and Program Information

Campus Map

A map of the campus is available on the Local Information page


Lecture Notes in Computer Science 9214/2015
“Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015 Proceedings."

Conference Schedule

Wednesday, August 5
Breakfast (On your own).
8:00 - 8:30 Registration (Elliott Building hallway)
8:30 - 9:30Plenary Talk 1
Room: Elliott 167
Chair: Ulrike Stege
Smoothed Analysis of Local Search Algorithms
Bodo Manthey
9:30 - 10:00Coffee Break (Hallway)
10:00 - 12:00 Session 1A
Room: Elliott 167
Chair: Faith Ellen
Session 1B
Room: Elliott 168
Chair: David Eppstein
The Complexity of Dominating Set Reconfiguration
Arash Haddadan, Takehiro Ito, Amer E.Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki and Youcef Tebbal
Convex Polygons in Geometric Triangulations
Adrian Dumitrescu and Csaba D. Tóth
Linearity is Strictly More Powerful than Contiguity for Encoding Graphs
Christophe Crespelle, Tien-Nam Le, Kevin Perrot and Thi Ha Duong Phan
Semi-dynamic Connectivity in the Plane
Sergio Cabello and Michael Kerber
On the Minimum Eccentricity Shortest Path Problem
Feodor Dragan and Arne Leitert
On the Chain Pair Simplification Problem
Chenglin Fan, Omtit Filtser, Matthew Katz, Tim Wylie and Binhai Zhu
Finding Articulation Points of Large Graphs in Linear Time
Martin Farach-Colton, Tsan-Sheng Hsu, Meng Li and Meng-Tsung Tsai
Elastic Geometric Shape Matching for Point Sets under Translations
Fabian Stehn and Christian Knauer
12:00 - 13:30Lunch (On your own)
13:30 - 15:00 Session 2A
Room: Elliott 167
Chair: Bodo Manthey
Session 2B
Room: Elliott 168
Chair: David Kirkpatrick
Positive Semidefinite Zero Forcing: Complexity and Lower Bounds
Boting Yang
LP-based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design
Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour and José A. Soto
A Moderately Exponential Time Algorithm for k-IBDD Satisfiability
Atsuki Nagao, Kazuhisa Seto and Junichi Teruyama
Non-Preemptive Scheduling on Machines with Setup Times
Alexander Mäcker, Manuel Malatyali, Friedhelm Meyer Auf der Heide and Sören Riechers
Online Bin Packing with Advice of Small Size
Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc Renault and Adi Rosén
Fast Universal Reconstruction of a String
Paweł Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
15:00 - 15:30Coffee Break (Hallway)
15:30 - 17:30 Session 3A
Room: Elliott 167
Chair: Ian Munro
Session 3B
Room: Elliott 168
Chair: Sue Whitesides
Dealing With 4-Variables by Resolution: An Improved MaxSAT Algorithm
Jianer Chen and Chao Xu
Fast and simple connectivity in graph timelines
Adam Karczmarz and Jakub Łacki
Solving Problems on Graphs of High Rank-Width
Eduard Eiben, Robert Ganian and Stefan Szeider
Cache-Oblivious Iterated Predecessor Queries via Range Coalescing
Erik D. Demaine, Vineet Gopal and William Hasenplaugh
On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids
Fahad Panolan, M. S. Ramanujan and Saket Saurabh
Optimal Shuffle Code with Permutation Instructions
Manuel Mohr, Sebastian Buchwald and Ignaz Rutter
The Parametric Closure Problem
David Eppstein
Dynamic Set Intersection
Tsvi Kopelowitz, Seth Pettie and Ely Porat
17:30 - 18:30NSERC Liaison Committee (Room: Elliott 167)

Thursday, August 6
Breakfast (On your own)
8:30 - 9:30Plenary Talk 2
Room: Elliott 167
Chair: Frank Dehne
Inferring People’s Social Behavior by Exploiting Their Spatiotemporal Location Data
Cyrus Shahabi
9:30 - 10:00Coffee Break (Hallway)
10:00 - 12:00 Session 4A
Room: Elliott 167
Chair: Binhai Zhu
Session 4B
Room: Elliott 168
Chair: Mike Goodrich
Generation of Colourings and Distinguishing Colourings of Graphs
William Bird and Wendy Myrvold
A New Approach for Contact Graph Representations and Its Applications
Yi-Jun Chang and Hsu-Chun Yen
Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara and Yushi Uno
An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs
Ahmad Biniaz, Anil Maheshwari, Michiel Smid and Subhas Nandy
On Conflict-Free Multi-Coloring
Andreas Bärtschi and Fabrizio Grandoni
On the Approximability of Orthogonal Order Preserving Layout Adjustment
Sayan Bandyapadhyay, Santanu Bhowmick and Kasturi Varadarajan
Rooted Cycle Bases
David Eppstein, J. Michael Mccarthy and Brian Parrish
On the Complexity of an Unregulated Traffic Crossing
Philip Dasler and David Mount
12:00 - 13:30Lunch (On your own)
13:30 - 15:00 Session 5A
Room: Elliott 167
Chair: Cyrus Shahabi
Session 5B
Room: Elliott 168
Chair: Adrian Dumitrescu
A 2k-Vertex Kernel for Maximum Internal Spanning Tree
Wenjun Li, Jianxin Wang, Jianer Chen and Yixin Cao
Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time
Gerth Stølting Brodal, Jesper Sindahl Nielsen and Jakob Truelsen
Reconfiguration on sparse graphs
Daniel Lokshtanov, Amer Mouawad, Fahad Panolan, M.S. Ramanujan and Saket Saurabh
Finding Pairwise Intersections Inside a Query Range
Mark de Berg, Joachim Gudmundsson and Ali D. Mehrabi
Competitive Diffusion on Weighted Graphs
Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka and Xiao Zhou
Sorting and Selection with Equality Comparisons
Varunkumar Jayapaul, Ian Munro, Venkatesh Raman and Srinivasa Rao Satti
15:00 - 21:00Excursion to Butchart Gardens and Conference Dinner at The Beach House

Friday, August 7
Breakfast (On your own)
8:30 - 9:30Plenary Talk 3
Room: Elliott 167
Chair: Joerg Sack
IMPORTANT UPDATE: Plenary Talk 3 has been postponed until 13:00. You can sleep in!
9:30 - 10:00Coffee Break (Hallway)
10:00 - 12:00 Session 6A
Room: Elliott 167
Chair: Will Evans
Session 6B
Room: Elliott 168
Chair: Saket Saurabh
Polynomial Delay Algorithm for Listing Minimal Edge Dominating sets in Graphs
Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine and Takeaki Uno
Time-Space Trade-offs for Triangulations and Voronoi Diagrams
Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth and Yannik Stein
Constant Time Enumeration by Amortization
Takeaki Uno
Contact Graphs of Circular Arcs
Md. Jawaherul Alam, David Eppstein, Michael Kaufmann, Stephen G. Kobourov, Sergey Pupyrev, André Schulz and Torsten Ueckerdt
Editing Graphs into Few Cliques: Complexity, Approximation, and Kernelization Schemes
Falk Hüffner, Christian Komusiewicz and André Nichterlein
Minimizing the Aggregate Movements for Interval Coverage
Aaron Andrews and Haitao Wang
Computing the Center of Uncertain Points on Tree Networks
Haitao Wang and Jingru Zhang
Approximating Nearest Neighbor Distances
Michael B. Cohen, Brittany Terese Fasy, Gary Miller, Amir Nayyeri, Don Sheehy and Ameya Velingker
12:00 - 13:00Lunch (On your own)
13:00 - 14:00Plenary Talk 3
Room: Elliott 167
Chair: Joerg Sack
Communication and Dynamic Networks
Bernard Chazelle
14:00 - 16:00 Session 7A
Room: Elliott 167
Chair: Bernard Chazelle
Session 7B
Room: Elliott 168
Chair: Wolfgang Mulzer
Greedy is an Almost Optimal Deque
Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, Laszlo Kozma and Thatchaphol Saranurak
On the Bounded-Hop Range Assignment Problem
Paz Carmi, Lilach Chaitman-Yerushalmi and Ohad Trabelsi
Polylogarithmic Fully Retroactive Priority Queues
Erik D. Demaine, Tim Kaler, Aaron Sidford, Quanquan Liu and Adam Yedidia
Straight-line Drawability of a Planar Graph Plus an Edge
Peter Eades, Seok-Hee Hong, Giuseppe Liotta, Naoki Katoh and Sheung-Hung Poon
Interval Selection in the Streaming Model
Sergio Cabello and Pablo Pérez-Lantero
Contact Representations of Non-Planar Graphs
Md. Jawaherul Alam, William Evans, Stephen Kobourov, Sergey Pupyrev, Jackson Toeniskoetter and Torsten Ueckerdt
Select with Groups of 3 or 4
Ke Chen and Adrian Dumitrescu

15:30 - 16:30Coffee Break (Hallway)
End of Conference