Portal - ESA 2020

ESA 2020	September 7-9, 2020, Pisa, Italy (Virtual Conference)
28th Annual European Symposium on Algorithms (ESA 2020) Fabrizio Grandoni and Grzegorz Herman and Peter Sanders (Eds.)
ISBN 978-3-95977-162-7, LIPICS Vol. 173	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 58 MB)
Search Publication Server

Authors

Chandrasekaran, Karthekeyan

Charalampopoulos, Panagiotis

Eisenbrand, Friedrich

Eube, Jan

Fairstein, Yaron

Fan, Chenglin

Feldmann, Andreas Emil

Fischer, Johannes

Flores-Velazco, Alejandro

Jiamjitrak, Wanchote Po

Kaaser, Dominik

Kale, Sagar

Kanté, Mamadou Moustapha

Komusiewicz, Christian

Manghiuc, Bogdan-Adrian

Mitchell, Joseph S. B.

Sahneh, Faryad Darabi

Thankachan, Sharma V.

Thilikos, Dimitrios M.

van der Grinten, Alexander

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Grandoni, Fabrizio ; Herman, Grzegorz ; Sanders, Peter

Abstract | Document (326 KB) | BibTeX

Planar Bichromatic Bottleneck Spanning Trees

Authors: Abu-Affash, A. Karim ; Bhore, Sujoy ; Carmi, Paz ; Mitchell, Joseph S. B.

Abstract | Document (962 KB) | BibTeX

Parallel Batch-Dynamic Trees via Change Propagation

Authors: Acar, Umut A. ; Anderson, Daniel ; Blelloch, Guy E. ; Dhulipala, Laxman ; Westrick, Sam

Abstract | Document (590 KB) | BibTeX

Reconstructing Biological and Digital Phylogenetic Trees in Parallel

Authors: Afshar, Ramtin ; Goodrich, Michael T. ; Matias, Pedro ; Osegueda, Martha C.

Abstract | Document (2,416 KB) | BibTeX

Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem

Authors: Ahmed, Reyan ; Sahneh, Faryad Darabi ; Hamm, Keaton ; Kobourov, Stephen ; Spence, Richard

Abstract | Document (1,680 KB) | BibTeX

Analysis of the Period Recovery Error Bound

Authors: Amir, Amihood ; Boneh, Itai ; Itzhaki, Michael ; Kondratovsky, Eitan

Abstract | Document (800 KB) | BibTeX

Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis

Authors: Angriman, Eugenio ; Predari, Maria ; van der Grinten, Alexander ; Meyerhenke, Henning

Abstract | Document (736 KB) | BibTeX

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

Authors: Arkin, Esther M. ; Das, Rathish ; Gao, Jie ; Goswami, Mayank ; Mitchell, Joseph S. B. ; Polishchuk, Valentin ; Tóth, Csaba D.

Abstract | Document (926 KB) | BibTeX

Set Cover with Delay - Clairvoyance Is Not Required

Authors: Azar, Yossi ; Chiplunkar, Ashish ; Kutten, Shay ; Touitou, Noam

Abstract | Document (601 KB) | BibTeX

Improved Bounds for Metric Capacitated Covering Problems

Authors: Bandyapadhyay, Sayan

Abstract | Document (450 KB) | BibTeX

Minimum Neighboring Degree Realization in Graphs and Trees

Authors: Bar-Noy, Amotz ; Choudhary, Keerti ; Cohen, Avi ; Peleg, David ; Rawitz, Dror

Abstract | Document (818 KB) | BibTeX

Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations

Authors: Barman, Siddharth ; Bhaskar, Umang ; Krishna, Anand ; Sundaram, Ranjani G.

Abstract | Document (603 KB) | BibTeX

Mincut Sensitivity Data Structures for the Insertion of an Edge

Authors: Baswana, Surender ; Gupta, Shiv ; Knollmann, Till

Abstract | Document (525 KB) | BibTeX

Linear Time LexDFS on Chordal Graphs

Authors: Beisegel, Jesse ; Köhler, Ekkehard ; Scheffler, Robert ; Strehler, Martin

Abstract | Document (497 KB) | BibTeX

Grundy Distinguishes Treewidth from Pathwidth

Authors: Belmonte, Rémy ; Kim, Eun Jung ; Lampis, Michael ; Mitsou, Valia ; Otachi, Yota

Abstract | Document (633 KB) | BibTeX

On the Complexity of BWT-Runs Minimization via Alphabet Reordering

Authors: Bentley, Jason W. ; Gibney, Daniel ; Thankachan, Sharma V.

Abstract | Document (541 KB) | BibTeX

Simulating Population Protocols in Sub-Constant Time per Interaction

Authors: Berenbrink, Petra ; Hammer, David ; Kaaser, Dominik ; Meyer, Ulrich ; Penschuck, Manuel ; Tran, Hung

Abstract | Document (754 KB) | BibTeX

An Optimal Decentralized (Δ + 1)-Coloring Algorithm

Authors: Bertschinger, Daniel ; Lengler, Johannes ; Martinsson, Anders ; Meier, Robert ; Steger, Angelika ; Trujić, Miloš ; Welzl, Emo

Abstract | Document (464 KB) | BibTeX

Noisy, Greedy and Not so Greedy k-Means++

Authors: Bhattacharya, Anup ; Eube, Jan ; Röglin, Heiko ; Schmidt, Melanie

Abstract | Document (530 KB) | BibTeX

An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling

Authors: Bhore, Sujoy ; Li, Guangping ; Nöllenburg, Martin

Abstract | Document (1,331 KB) | BibTeX

Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies

Authors: Blum, Johannes ; Storandt, Sabine

Abstract | Document (435 KB) | BibTeX

The Minimization of Random Hypergraphs

Authors: Bläsius, Thomas ; Friedrich, Tobias ; Schirneck, Martin

Abstract | Document (650 KB) | BibTeX

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs

Authors: Bok, Jan ; Jedlic̆ková, Nikola ; Martin, Barnaby ; Paulusma, Daniël ; Smith, Siani

Abstract | Document (806 KB) | BibTeX

An Algorithmic Weakening of the Erdős-Hajnal Conjecture

Authors: Bonnet, Édouard ; Thomassé, Stéphan ; Tran, Xuan Thang ; Watrigant, Rémi

Abstract | Document (652 KB) | BibTeX

Reconfiguration of Spanning Trees with Many or Few Leaves

Authors: Bousquet, Nicolas ; Ito, Takehiro ; Kobayashi, Yusuke ; Mizuta, Haruka ; Ouvrard, Paul ; Suzuki, Akira ; Wasa, Kunihiro

Abstract | Document (864 KB) | BibTeX

When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation

Authors: Bringmann, Karl ; Künnemann, Marvin ; Nusser, André

Abstract | Document (1,236 KB) | BibTeX

Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice

Authors: Brooksbank, Peter A. ; Li, Yinan ; Qiao, Youming ; Wilson, James B.

Abstract | Document (554 KB) | BibTeX

Sometimes Reliable Spanners of Almost Linear Size

Authors: Buchin, Kevin ; Har-Peled, Sariel ; Oláh, Dániel

Abstract | Document (577 KB) | BibTeX

New Binary Search Tree Bounds via Geometric Inversions

Authors: Chalermsook, Parinya ; Jiamjitrak, Wanchote Po

Abstract | Document (911 KB) | BibTeX

More on Change-Making and Related Problems

Authors: Chan, Timothy M. ; He, Qizheng

Abstract | Document (533 KB) | BibTeX

The Maximum Binary Tree Problem

Authors: Chandrasekaran, Karthekeyan ; Grigorescu, Elena ; Istrate, Gabriel ; Kulkarni, Shubhang ; Lin, Young-San ; Zhu, Minshen

Abstract | Document (645 KB) | BibTeX

Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs

Authors: Charalampopoulos, Panagiotis ; Karczmarz, Adam

Abstract | Document (553 KB) | BibTeX

The Number of Repetitions in 2D-Strings

Authors: Charalampopoulos, Panagiotis ; Radoszewski, Jakub ; Rytter, Wojciech ; Waleń, Tomasz ; Zuba, Wiktor

Abstract | Document (621 KB) | BibTeX

New Bounds on Augmenting Steps of Block-Structured Integer Programs

Authors: Chen, Lin ; Koutecký, Martin ; Xu, Lei ; Shi, Weidong

Abstract | Document (631 KB) | BibTeX

Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays

Authors: Chiu, Man-Kwun ; Korman, Matias ; Suderland, Martin ; Tokuyama, Takeshi

Abstract | Document (905 KB) | BibTeX

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes

Authors: Chudnovsky, Maria ; King, Jason ; Pilipczuk, Michał ; Rzążewski, Paweł ; Spirkl, Sophie

Abstract | Document (951 KB) | BibTeX

Compact Oblivious Routing in Weighted Graphs

Authors: Czerner, Philipp ; Räcke, Harald

Abstract | Document (565 KB) | BibTeX

Approximation Algorithms for Clustering with Dynamic Points

Authors: Deng, Shichuan ; Li, Jian ; Rabani, Yuval

Abstract | Document (541 KB) | BibTeX

A Sub-Linear Time Framework for Geometric Optimization with Outliers in High Dimensions

Authors: Ding, Hu

Abstract | Document (774 KB) | BibTeX

Practical Performance of Space Efficient Data Structures for Longest Common Extensions

Authors: Dinklage, Patrick ; Fischer, Johannes ; Herlez, Alexander ; Kociumaka, Tomasz ; Kurpicz, Florian

Abstract | Document (704 KB) | BibTeX

First-Order Model-Checking in Random Graphs and Complex Networks

Authors: Dreier, Jan ; Kuinke, Philipp ; Rossmanith, Peter

Abstract | Document (568 KB) | BibTeX

Optimally Handling Commitment Issues in Online Throughput Maximization

Authors: Eberle, Franziska ; Megow, Nicole ; Schewior, Kevin

Abstract | Document (601 KB) | BibTeX

A Polynomial Kernel for Line Graph Deletion

Authors: Eiben, Eduard ; Lochet, William

Abstract | Document (570 KB) | BibTeX

Approximate CVP_p in Time 2^{0.802 n}

Authors: Eisenbrand, Friedrich ; Venzin, Moritz

Abstract | Document (717 KB) | BibTeX

A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem

Authors: Fairstein, Yaron ; Kulik, Ariel ; Naor, Joseph (Seffi) ; Raz, Danny ; Shachnai, Hadas

Abstract | Document (581 KB) | BibTeX

Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams

Authors: Fan, Chenglin ; Raichel, Benjamin

Abstract | Document (632 KB) | BibTeX

Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs

Authors: Feldmann, Andreas Emil ; Saulpic, David

Abstract | Document (616 KB) | BibTeX

Coresets for the Nearest-Neighbor Rule

Authors: Flores-Velazco, Alejandro ; Mount, David M.

Abstract | Document (4,988 KB) | BibTeX

Kernelization of Whitney Switches

Authors: Fomin, Fedor V. ; Golovach, Petr A.

Abstract | Document (746 KB) | BibTeX

Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs

Authors: Fomin, Fedor V. ; Golovach, Petr A.

Abstract | Document (609 KB) | BibTeX

On the Complexity of Recovering Incidence Matrices

Authors: Fomin, Fedor V. ; Golovach, Petr ; Misra, Pranabendu ; Ramanujan, M. S.

Abstract | Document (597 KB) | BibTeX

An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Stamoulis, Giannos ; Thilikos, Dimitrios M.

Abstract | Document (1,265 KB) | BibTeX

A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time

Authors: Friggstad, Zachary ; Swamy, Chaitanya

Abstract | Document (1,085 KB) | BibTeX

On Compact RAC Drawings

Authors: Förster, Henry ; Kaufmann, Michael

Abstract | Document (1,319 KB) | BibTeX

Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing

Authors: Gao, Younan ; He, Meng ; Nekrich, Yakov

Abstract | Document (562 KB) | BibTeX

Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow

Authors: Garg, Naveen ; Kumar, Nikhil

Abstract | Document (565 KB) | BibTeX

An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams

Authors: Held, Martin ; de Lorenzo, Stefan

Abstract | Document (2,244 KB) | BibTeX

Fully-Dynamic Coresets

Authors: Henzinger, Monika ; Kale, Sagar

Abstract | Document (559 KB) | BibTeX

Dynamic Matching Algorithms in Practice

Authors: Henzinger, Monika ; Khan, Shahbaz ; Paul, Richard ; Schulz, Christian

Abstract | Document (1,083 KB) | BibTeX

Finding All Global Minimum Cuts in Practice

Authors: Henzinger, Monika ; Noe, Alexander ; Schulz, Christian ; Strash, Darren

Abstract | Document (685 KB) | BibTeX

Approximate Turing Kernelization for Problems Parameterized by Treewidth

Authors: Hols, Eva-Maria C. ; Kratsch, Stefan ; Pieterse, Astrid

Abstract | Document (700 KB) | BibTeX

The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance

Authors: Hoppenworth, Gary ; Bentley, Jason W. ; Gibney, Daniel ; Thankachan, Sharma V.

Abstract | Document (621 KB) | BibTeX

Capacitated Sum-Of-Radii Clustering: An FPT Approximation

Authors: Inamdar, Tanmay ; Varadarajan, Kasturi

Abstract | Document (550 KB) | BibTeX

Optimal Polynomial-Time Compression for Boolean Max CSP

Authors: Jansen, Bart M. P. ; Włodarczyk, Michał

Abstract | Document (831 KB) | BibTeX

A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth

Authors: Kanté, Mamadou Moustapha ; Paul, Christophe ; Thilikos, Dimitrios M.

Abstract | Document (719 KB) | BibTeX

Exploiting c-Closure in Kernelization Algorithms for Graph Problems

Authors: Koana, Tomohiro ; Komusiewicz, Christian ; Sommer, Frank

Abstract | Document (536 KB) | BibTeX

Many Visits TSP Revisited

Authors: Kowalik, Łukasz ; Li, Shaohua ; Nadara, Wojciech ; Smulewicz, Marcin ; Wahlström, Magnus

Abstract | Document (974 KB) | BibTeX

Light Euclidean Spanners with Steiner Points

Authors: Le, Hung ; Solomon, Shay

Abstract | Document (590 KB) | BibTeX

Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality

Authors: Lecomte, Victor ; Weinstein, Omri

Abstract | Document (601 KB) | BibTeX

On the Computational Complexity of Linear Discrepancy

Authors: Li, Lily ; Nikolov, Aleksandar

Abstract | Document (608 KB) | BibTeX

Augmenting the Algebraic Connectivity of Graphs

Authors: Manghiuc, Bogdan-Adrian ; Peng, Pan ; Sun, He

Abstract | Document (686 KB) | BibTeX

Chordless Cycle Packing Is Fixed-Parameter Tractable

Authors: Marx, Dániel

Abstract | Document (553 KB) | BibTeX

Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy

Authors: Marx, Dániel ; Sandeep, R. B.

Abstract | Document (684 KB) | BibTeX

Approximating k-Connected m-Dominating Sets

Authors: Nutov, Zeev

Abstract | Document (635 KB) | BibTeX

Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs

Authors: Okrasa, Karolina ; Piecyk, Marta ; Rzążewski, Paweł

Abstract | Document (621 KB) | BibTeX

Generalizing CGAL Periodic Delaunay Triangulations

Authors: Osang, Georg ; Rouxel-Labbé, Mael ; Teillaud, Monique

Abstract | Document (716 KB) | BibTeX

Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching

Authors: Panagiotas, Ioannis ; Uçar, Bora

Abstract | Document (754 KB) | BibTeX

Efficient Computation of 2-Covers of a String

Authors: Radoszewski, Jakub ; Straszyński, Juliusz

Abstract | Document (620 KB) | BibTeX

Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions

Authors: Raman, Rajiv ; Ray, Saurabh

Abstract | Document (516 KB) | BibTeX

Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time

Authors: Ren, Hanlin

Abstract | Document (594 KB) | BibTeX

Fine-Grained Complexity of Regular Expression Pattern Matching and Membership

Authors: Schepper, Philipp

Abstract | Document (875 KB) | BibTeX

Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks

Authors: Strasser, Ben ; Wagner, Dorothea ; Zeitz, Tim

Abstract | Document (434 KB) | BibTeX

Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents

Authors: Zhang, Hanrui

Abstract | Document (464 KB) | BibTeX

On the Approximation Ratio of the k-Opt and Lin-Kernighan Algorithm for Metric and Graph TSP

Authors: Zhong, Xianghui

Abstract | Document (524 KB) | BibTeX

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

28th Annual European Symposium on Algorithms (ESA 2020)