![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
28th ESA 2020: Pisa, Italy (Virtual Conference)
- Fabrizio Grandoni
, Grzegorz Herman
, Peter Sanders
:
28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference). LIPIcs 173, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-162-7 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:20
- A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, Joseph S. B. Mitchell:
Planar Bichromatic Bottleneck Spanning Trees. 1:1-1:16 - Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Sam Westrick
:
Parallel Batch-Dynamic Trees via Change Propagation. 2:1-2:23 - Ramtin Afshar
, Michael T. Goodrich
, Pedro Matias
, Martha C. Osegueda
:
Reconstructing Biological and Digital Phylogenetic Trees in Parallel. 3:1-3:24 - Abu Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen G. Kobourov
, Richard Spence
:
Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem. 4:1-4:21 - Amihood Amir, Itai Boneh, Michael Itzhaki, Eitan Kondratovsky:
Analysis of the Period Recovery Error Bound. 5:1-5:21 - Eugenio Angriman
, Maria Predari
, Alexander van der Grinten
, Henning Meyerhenke
:
Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis. 6:1-6:24 - Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, Csaba D. Tóth:
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization. 7:1-7:23 - Yossi Azar, Ashish Chiplunkar, Shay Kutten, Noam Touitou
:
Set Cover with Delay - Clairvoyance Is Not Required. 8:1-8:21 - Sayan Bandyapadhyay
:
Improved Bounds for Metric Capacitated Covering Problems. 9:1-9:17 - Amotz Bar-Noy, Keerti Choudhary
, Avi Cohen, David Peleg, Dror Rawitz:
Minimum Neighboring Degree Realization in Graphs and Trees. 10:1-10:15 - Siddharth Barman, Umang Bhaskar, Anand Krishna, Ranjani G. Sundaram:
Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations. 11:1-11:17 - Surender Baswana
, Shiv Kumar Gupta, Till Knollmann
:
Mincut Sensitivity Data Structures for the Insertion of an Edge. 12:1-12:14 - Jesse Beisegel, Ekkehard Köhler, Robert Scheffler
, Martin Strehler
:
Linear Time LexDFS on Chordal Graphs. 13:1-13:13 - Rémy Belmonte, Eun Jung Kim, Michael Lampis
, Valia Mitsou, Yota Otachi
:
Grundy Distinguishes Treewidth from Pathwidth. 14:1-14:19 - Jason W. Bentley
, Daniel Gibney, Sharma V. Thankachan:
On the Complexity of BWT-Runs Minimization via Alphabet Reordering. 15:1-15:13 - Petra Berenbrink, David Hammer
, Dominik Kaaser
, Ulrich Meyer, Manuel Penschuck, Hung Tran:
Simulating Population Protocols in Sub-Constant Time per Interaction. 16:1-16:22 - Daniel Bertschinger, Johannes Lengler
, Anders Martinsson, Robert Meier, Angelika Steger, Milos Trujic
, Emo Welzl:
An Optimal Decentralized (Δ + 1)-Coloring Algorithm. 17:1-17:12 - Anup Bhattacharya, Jan Eube, Heiko Röglin
, Melanie Schmidt
:
Noisy, Greedy and Not so Greedy k-Means++. 18:1-18:21 - Sujoy Bhore
, Guangping Li
, Martin Nöllenburg
:
An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling. 19:1-19:24 - Johannes Blum
, Sabine Storandt:
Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies. 20:1-20:14 - Thomas Bläsius, Tobias Friedrich
, Martin Schirneck
:
The Minimization of Random Hypergraphs. 21:1-21:15 - Jan Bok
, Nikola Jedlicková
, Barnaby Martin, Daniël Paulusma
, Siani Smith
:
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. 22:1-22:22 - Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant:
An Algorithmic Weakening of the Erdős-Hajnal Conjecture. 23:1-23:18 - Nicolas Bousquet
, Takehiro Ito
, Yusuke Kobayashi
, Haruka Mizuta, Paul Ouvrard, Akira Suzuki
, Kunihiro Wasa
:
Reconfiguration of Spanning Trees with Many or Few Leaves. 24:1-24:15 - Karl Bringmann, Marvin Künnemann, André Nusser:
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation. 25:1-25:17 - Peter A. Brooksbank
, Yinan Li, Youming Qiao
, James B. Wilson
:
Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice. 26:1-26:15 - Kevin Buchin, Sariel Har-Peled
, Dániel Oláh:
Sometimes Reliable Spanners of Almost Linear Size. 27:1-27:15 - Parinya Chalermsook, Wanchote Po Jiamjitrak:
New Binary Search Tree Bounds via Geometric Inversions. 28:1-28:16 - Timothy M. Chan
, Qizheng He:
More on Change-Making and Related Problems. 29:1-29:14 - Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu:
The Maximum Binary Tree Problem. 30:1-30:22 - Panagiotis Charalampopoulos
, Adam Karczmarz
:
Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. 31:1-31:23 - Panagiotis Charalampopoulos
, Jakub Radoszewski
, Wojciech Rytter
, Tomasz Walen
, Wiktor Zuba
:
The Number of Repetitions in 2D-Strings. 32:1-32:18 - Lin Chen
, Martin Koutecký
, Lei Xu
, Weidong Shi:
New Bounds on Augmenting Steps of Block-Structured Integer Programs. 33:1-33:19 - Man-Kwun Chiu
, Matias Korman, Martin Suderland
, Takeshi Tokuyama
:
Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays. 34:1-34:22 - Maria Chudnovsky
, Jason King, Michal Pilipczuk, Pawel Rzazewski
, Sophie Spirkl:
Finding Large H-Colorable Subgraphs in Hereditary Graph Classes. 35:1-35:17 - Philipp Czerner
, Harald Räcke:
Compact Oblivious Routing in Weighted Graphs. 36:1-36:23 - Shichuan Deng, Jian Li, Yuval Rabani:
Approximation Algorithms for Clustering with Dynamic Points. 37:1-37:15 - Hu Ding
:
A Sub-Linear Time Framework for Geometric Optimization with Outliers in High Dimensions. 38:1-38:21 - Patrick Dinklage
, Johannes Fischer, Alexander Herlez
, Tomasz Kociumaka
, Florian Kurpicz
:
Practical Performance of Space Efficient Data Structures for Longest Common Extensions. 39:1-39:20 - Jan Dreier
, Philipp Kuinke
, Peter Rossmanith
:
First-Order Model-Checking in Random Graphs and Complex Networks. 40:1-40:23 - Franziska Eberle
, Nicole Megow
, Kevin Schewior
:
Optimally Handling Commitment Issues in Online Throughput Maximization. 41:1-41:15 - Eduard Eiben
, William Lochet
:
A Polynomial Kernel for Line Graph Deletion. 42:1-42:15 - Friedrich Eisenbrand, Moritz Venzin:
Approximate CVPp in Time 20.802 n. 43:1-43:15 - Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, Hadas Shachnai:
A (1-e-1-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem. 44:1-44:19 - Chenglin Fan, Benjamin Raichel:
Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams. 45:1-45:18 - Andreas Emil Feldmann
, David Saulpic
:
Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs. 46:1-46:22 - Alejandro Flores-Velazco
, David M. Mount
:
Coresets for the Nearest-Neighbor Rule. 47:1-47:19 - Fedor V. Fomin
, Petr A. Golovach
:
Kernelization of Whitney Switches. 48:1-48:19 - Fedor V. Fomin
, Petr A. Golovach
:
Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. 49:1-49:17 - Fedor V. Fomin
, Petr A. Golovach, Pranabendu Misra, M. S. Ramanujan:
On the Complexity of Recovering Incidence Matrices. 50:1-50:13 - Fedor V. Fomin
, Petr A. Golovach, Giannos Stamoulis
, Dimitrios M. Thilikos:
An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL. 51:1-51:17 - Zachary Friggstad, Chaitanya Swamy:
A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time. 52:1-52:20 - Henry Förster
, Michael Kaufmann
:
On Compact RAC Drawings. 53:1-53:21 - Younan Gao
, Meng He
, Yakov Nekrich
:
Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing. 54:1-54:18 - Naveen Garg
, Nikhil Kumar:
Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow. 55:1-55:13 - Martin Held
, Stefan de Lorenzo
:
An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams. 56:1-56:15 - Monika Henzinger
, Sagar Kale
:
Fully-Dynamic Coresets. 57:1-57:21 - Monika Henzinger
, Shahbaz Khan
, Richard Paul
, Christian Schulz
:
Dynamic Matching Algorithms in Practice. 58:1-58:20 - Monika Henzinger
, Alexander Noe
, Christian Schulz
, Darren Strash
:
Finding All Global Minimum Cuts in Practice. 59:1-59:20 - Eva-Maria C. Hols
, Stefan Kratsch
, Astrid Pieterse
:
Approximate Turing Kernelization for Problems Parameterized by Treewidth. 60:1-60:23 - Gary Hoppenworth, Jason W. Bentley
, Daniel Gibney, Sharma V. Thankachan:
The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance. 61:1-61:19 - Tanmay Inamdar, Kasturi R. Varadarajan:
Capacitated Sum-Of-Radii Clustering: An FPT Approximation. 62:1-62:17 - Bart M. P. Jansen
, Michal Wlodarczyk
:
Optimal Polynomial-Time Compression for Boolean Max CSP. 63:1-63:19 - Mamadou Moustapha Kanté
, Christophe Paul
, Dimitrios M. Thilikos
:
A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth. 64:1-64:16 - Tomohiro Koana
, Christian Komusiewicz
, Frank Sommer
:
Exploiting c-Closure in Kernelization Algorithms for Graph Problems. 65:1-65:17 - Lukasz Kowalik
, Shaohua Li
, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström
:
Many Visits TSP Revisited. 66:1-66:22 - Hung Le, Shay Solomon:
Light Euclidean Spanners with Steiner Points. 67:1-67:22 - Victor Lecomte, Omri Weinstein:
Settling the Relationship Between Wilber's Bounds for Dynamic Optimality. 68:1-68:21 - Lily Li, Aleksandar Nikolov:
On the Computational Complexity of Linear Discrepancy. 69:1-69:16 - Bogdan-Adrian Manghiuc
, Pan Peng
, He Sun:
Augmenting the Algebraic Connectivity of Graphs. 70:1-70:22 - Dániel Marx:
Chordless Cycle Packing Is Fixed-Parameter Tractable. 71:1-71:19 - Dániel Marx, R. B. Sandeep:
Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy. 72:1-72:25 - Zeev Nutov:
Approximating k-Connected m-Dominating Sets. 73:1-73:14 - Karolina Okrasa
, Marta Piecyk
, Pawel Rzazewski
:
Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs. 74:1-74:24 - Georg Osang
, Mael Rouxel-Labbé, Monique Teillaud
:
Generalizing CGAL Periodic Delaunay Triangulations. 75:1-75:17 - Ioannis Panagiotas
, Bora Uçar:
Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching. 76:1-76:23 - Jakub Radoszewski
, Juliusz Straszynski
:
Efficient Computation of 2-Covers of a String. 77:1-77:17 - Rajiv Raman, Saurabh Ray:
Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. 78:1-78:16 - Hanlin Ren
:
Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. 79:1-79:13 - Philipp Schepper
:
Fine-Grained Complexity of Regular Expression Pattern Matching and Membership. 80:1-80:20 - Ben Strasser, Dorothea Wagner, Tim Zeitz
:
Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks. 81:1-81:14 - Hanrui Zhang:
Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents. 82:1-82:17 - Xianghui Zhong
:
On the Approximation Ratio of the k-Opt and Lin-Kernighan Algorithm for Metric and Graph TSP. 83:1-83:13
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.