Print

SWAT 2020 Program

All times are in Western European Summer Time.

Day 1: 22nd June

 

Session 1

  • 9:20 – 9:45 "Low-stretch spanning trees of graphs with bounded width", Glencora Borradaile, David Eppstein, William Maxwell and Amir Nayyeri.
  • 9:45 – 10:10 "A Simple Algorithm for Minimum Cuts in Near-Linear Time", Antonio Molina Lovett and Bryce Sandlund.
  • 10:10 – 10:35 "Graph Realizations: Maximum Degree in Vertex Neighborhoods", Amotz Bar-Noy, Keerti Choudhary, David Peleg and Dror Rawitz.
  • 10:35 – 11:00 "Simplifying Activity-on-Edge Graphs", David Eppstein, Daniel Frishberg and Elham Havvaei.

Break: 11:00 – 11:10

Session 2: Invited Talk

  • 11:10 - 12:00 "Parameterized Complexity of PCA", Fedor Fomin.

Session 3

  • 13:00 - 13:25 "Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives", Nader Bshouty, Catherine Haddad-Zaknoon, Raghd Boulos, Foad Moalem, Jalal Nada, Elias Noufi and Yara Zaknoon.
  • 13:25 - 13:50 "Fast Multi-Subset Transform and Weighted Sums Over Acyclic Digraphs", Mikko Koivisto and Antti Röyskö.
  • 13:50 – 14:15 "Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams", Seiichiro Tani.

Break: 14:15 – 14:25

Session 4

  • 14:25 – 14:50 "Preprocessing Vertex Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies", Bart M. P. Jansen and Jari J.H. de Kroon.
  • 14:50 – 15:15 "On the Parameterized Complexity of Grid Contraction", Saket Saurabh, Uéverton Dos Santos Souza and Prafullkumar Tale.
  • 15:15 – 15:40 "Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-
    Degree Graphs", Niels Grüttemeier, Christian Komusiewicz and Nils Morawietz.
  • 15:40 – 16:05 "Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time", Max Bannach, Malte Skambath and Till Tantau.

 

Day 2: 23rd June

 

Session 5

  • 9:20 – 9:45 "Parameter Analysis for Guarding Terrain", Akanksha Agrawal, Sudeshna Kolay and Meirav Zehavi.
  • 9:45 – 10:10 "Trajectory Visibility", Patrick Eades, Ivor van der Hoog, Maarten Löffler and Frank Staals.
  • 10:10 – 10:35 "Simplification of Polyline Bundles", Joachim Spoerhase, Sabine Storandt and Johannes Zink.
  • 10:35 – 11:00 "Sparse Regression via Range Counting", Jean Cardinal and Aurélien Ooms

Break: 11:00 – 11:10

Session 6: Invited Talk

  • 11:10 - 12:00 "Landscape of Locality", Jukka Suomela.

Break: 12:00 – 13:00

Session 7

  • 13:00 - 13:25 "Exact exponential algorithms for two poset problems", László Kozma.
  • 13:25 - 13:50 "Parameterized Complexity of Two-Interval Pattern Problem", Prosenjit Bose, Saeed Mehrabi and Debajyoti Mondal.
  • 13:50 – 14:15 "Parameterized Study of Steiner Tree on Unit Disk Graphs", Sujoy Bhore, Paz Carmi, Sudeshna Kolay and Meirav Zehavi.

Break: 14:15 – 14:25

Session 8

  • 14:25 – 14:50 "Vertex Downgrading to Minimize Connectivity", Da Qi Chen, R. Ravi and Hassene Aissi.
  • 14:50 – 15:15 "Bounded-Angle Minimum Spanning Trees", Ahmad Biniaz, Prosenjit Bose, Anna Lubiw and Anil Maheshwari.
  • 15:15 – 15:40 "Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem", Sivakumar Rathinam, R Ravi, Jung Yun Bae and Kaarthik Sundar.
  • 15:40 – 16:05 "Online embedding of metrics", Ilan Newman and Yuri Rabinovich.

 

Day 3: 24th June

 

Session 9

  • 9:20 – 9:45 "A Dynamic Space-Efficient Filter with Constant Time Operations", Ioana Bercea and Guy Even.
  • 9:45 – 10:10 "Locality Sensitive Hashing for set-queries, motivated by group recommendations", Haim Kaplan and Jay Tenenbaum.
  • 10:10 – 10:35 "Space-Efficient Data Structures for Lattices", Ian Munro, Bryce Sandlund and Corwin Sinnamon.
  • 10:35 – 11:00 "Sea-rise Flooding on Massive", Lars Arge, Mathias Rav, Morten Revsbæk, Yujin Shin and Jungwoo Yang

Break: 11:00 – 11:10

Session 10

  • 11:10 – 11:35 "Submodular Clustering in Low Dimensions", Arturs Backurs and Sariel Har-Peled.
  • 11:35 – 12:00 "Preclustering Algorithms for Imprecise Points", Mohammad Ali Abam, Mark de Berg, Sina Farahzad, Mir Omid Haji Mirsadeghi and Morteza Saghafian.
  • 12:00 – 12:25 "On the hardness of computing an average curve", Kevin Buchin, Anne Driemel and Martijn Struijs.
  • 12:25 – 12:50 "Clustering Moving Entities in Euclidean Space", Stephane Durocher and Md Yeakub Hassan.

Break: 12:50 – 13:30

Session 11

  • 13:30 – 13:55 "Generalized Metric Repair on Graphs", Chenglin Fan, Anna Gilbert, Benjamin Raichel, Rishi Sonthalia and Gregory Van Buskirk.
  • 13:55 – 14:20 "Recoloring Interval Graphs with Limited Recourse Budget", Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz and Anna Zych-Pawlewicz.
  • 14:20 – 14:45 "Drawing Graphs with Circular Arcs and Right Angle Crossings", Steven Chaplick, Myroslav Kryven, Henry Förster and Alexander Wolff.
  • 14:45 – 15:10 "Computing β-Stretch Paths in Drawings of Graphs", Esther Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov and Joseph S.B. Mitchell.

Conference ends