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
  • Abu-Affash, A. Karim
  • Acar, Umut A.
  • Afshar, Ramtin
  • Ahmed, Reyan
  • Amir, Amihood
  • Anderson, Daniel
  • Angriman, Eugenio
  • Arkin, Esther M.
  • Azar, Yossi
  • Bandyapadhyay, Sayan
  • Barman, Siddharth
  • Bar-Noy, Amotz
  • Baswana, Surender
  • Beisegel, Jesse
  • Belmonte, Rémy
  • Bentley, Jason W.
  • Berenbrink, Petra
  • Bertschinger, Daniel
  • Bhaskar, Umang
  • Bhattacharya, Anup
  • Bhore, Sujoy
  • Bläsius, Thomas
  • Blelloch, Guy E.
  • Blum, Johannes
  • Bok, Jan
  • Boneh, Itai
  • Bonnet, Édouard
  • Bousquet, Nicolas
  • Bringmann, Karl
  • Brooksbank, Peter A.
  • Buchin, Kevin
  • Carmi, Paz
  • Chalermsook, Parinya
  • Chandrasekaran, Karthekeyan
  • Chan, Timothy M.
  • Charalampopoulos, Panagiotis
  • Chen, Lin
  • Chiplunkar, Ashish
  • Chiu, Man-Kwun
  • Choudhary, Keerti
  • Chudnovsky, Maria
  • Cohen, Avi
  • Czerner, Philipp
  • Das, Rathish
  • de Lorenzo, Stefan
  • Deng, Shichuan
  • Dhulipala, Laxman
  • Ding, Hu
  • Dinklage, Patrick
  • Dreier, Jan
  • Eberle, Franziska
  • Eiben, Eduard
  • Eisenbrand, Friedrich
  • Eube, Jan
  • Fairstein, Yaron
  • Fan, Chenglin
  • Feldmann, Andreas Emil
  • Fischer, Johannes
  • Flores-Velazco, Alejandro
  • Fomin, Fedor V.
  • Förster, Henry
  • Friedrich, Tobias
  • Friggstad, Zachary
  • Gao, Jie
  • Gao, Younan
  • Garg, Naveen
  • Gibney, Daniel
  • Golovach, Petr
  • Golovach, Petr A.
  • Goodrich, Michael T.
  • Goswami, Mayank
  • Grandoni, Fabrizio
  • Grigorescu, Elena
  • Gupta, Shiv
  • Hammer, David
  • Hamm, Keaton
  • Har-Peled, Sariel
  • Held, Martin
  • He, Meng
  • Henzinger, Monika
  • He, Qizheng
  • Herlez, Alexander
  • Herman, Grzegorz
  • Hols, Eva-Maria C.
  • Hoppenworth, Gary
  • Inamdar, Tanmay
  • Istrate, Gabriel
  • Ito, Takehiro
  • Itzhaki, Michael
  • Jansen, Bart M. P.
  • Jedlic̆ková, Nikola
  • Jiamjitrak, Wanchote Po
  • Kaaser, Dominik
  • Kale, Sagar
  • Kanté, Mamadou Moustapha
  • Karczmarz, Adam
  • Kaufmann, Michael
  • Khan, Shahbaz
  • Kim, Eun Jung
  • King, Jason
  • Knollmann, Till
  • Koana, Tomohiro
  • Kobayashi, Yusuke
  • Kobourov, Stephen
  • Kociumaka, Tomasz
  • Köhler, Ekkehard
  • Komusiewicz, Christian
  • Kondratovsky, Eitan
  • Korman, Matias
  • Koutecký, Martin
  • Kowalik, Łukasz
  • Kratsch, Stefan
  • Krishna, Anand
  • Kuinke, Philipp
  • Kulik, Ariel
  • Kulkarni, Shubhang
  • Kumar, Nikhil
  • Künnemann, Marvin
  • Kurpicz, Florian
  • Kutten, Shay
  • Lampis, Michael
  • Lecomte, Victor
  • Le, Hung
  • Lengler, Johannes
  • Li, Guangping
  • Li, Jian
  • Li, Lily
  • Lin, Young-San
  • Li, Shaohua
  • Li, Yinan
  • Lochet, William
  • Manghiuc, Bogdan-Adrian
  • Martin, Barnaby
  • Martinsson, Anders
  • Marx, Dániel
  • Matias, Pedro
  • Megow, Nicole
  • Meier, Robert
  • Meyerhenke, Henning
  • Meyer, Ulrich
  • Misra, Pranabendu
  • Mitchell, Joseph S. B.
  • Mitsou, Valia
  • Mizuta, Haruka
  • Mount, David M.
  • Nadara, Wojciech
  • Naor, Joseph (Seffi)
  • Nekrich, Yakov
  • Nikolov, Aleksandar
  • Noe, Alexander
  • Nöllenburg, Martin
  • Nusser, André
  • Nutov, Zeev
  • Okrasa, Karolina
  • Oláh, Dániel
  • Osang, Georg
  • Osegueda, Martha C.
  • Otachi, Yota
  • Ouvrard, Paul
  • Panagiotas, Ioannis
  • Paul, Christophe
  • Paul, Richard
  • Paulusma, Daniël
  • Peleg, David
  • Peng, Pan
  • Penschuck, Manuel
  • Piecyk, Marta
  • Pieterse, Astrid
  • Pilipczuk, Michał
  • Polishchuk, Valentin
  • Predari, Maria
  • Qiao, Youming
  • Rabani, Yuval
  • Räcke, Harald
  • Radoszewski, Jakub
  • Raichel, Benjamin
  • Raman, Rajiv
  • Ramanujan, M. S.
  • Rawitz, Dror
  • Ray, Saurabh
  • Raz, Danny
  • Ren, Hanlin
  • Röglin, Heiko
  • Rossmanith, Peter
  • Rouxel-Labbé, Mael
  • Rytter, Wojciech
  • Rzążewski, Paweł
  • Sahneh, Faryad Darabi
  • Sandeep, R. B.
  • Sanders, Peter
  • Saulpic, David
  • Scheffler, Robert
  • Schepper, Philipp
  • Schewior, Kevin
  • Schirneck, Martin
  • Schmidt, Melanie
  • Schulz, Christian
  • Shachnai, Hadas
  • Shi, Weidong
  • Smith, Siani
  • Smulewicz, Marcin
  • Solomon, Shay
  • Sommer, Frank
  • Spence, Richard
  • Spirkl, Sophie
  • Stamoulis, Giannos
  • Steger, Angelika
  • Storandt, Sabine
  • Strash, Darren
  • Strasser, Ben
  • Straszyński, Juliusz
  • Strehler, Martin
  • Suderland, Martin
  • Sundaram, Ranjani G.
  • Sun, He
  • Suzuki, Akira
  • Swamy, Chaitanya
  • Teillaud, Monique
  • Thankachan, Sharma V.
  • Thilikos, Dimitrios M.
  • Thomassé, Stéphan
  • Tokuyama, Takeshi
  • Tóth, Csaba D.
  • Touitou, Noam
  • Tran, Hung
  • Tran, Xuan Thang
  • Trujić, Miloš
  • Uçar, Bora
  • van der Grinten, Alexander
  • Varadarajan, Kasturi
  • Venzin, Moritz
  • Wagner, Dorothea
  • Wahlström, Magnus
  • Waleń, Tomasz
  • Wasa, Kunihiro
  • Watrigant, Rémi
  • Weinstein, Omri
  • Welzl, Emo
  • Westrick, Sam
  • Wilson, James B.
  • Włodarczyk, Michał
  • Xu, Lei
  • Zeitz, Tim
  • Zhang, Hanrui
  • Zhong, Xianghui
  • Zhu, Minshen
  • Zuba, Wiktor

  •   
    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