ISAAC 2021 December 6-8, 2021, Fukuoka, Japan

32nd International Symposium on Algorithms and Computation (ISAAC 2021)



Hee-Kap Ahn and Kunihiko Sadakane (Eds.)
ISBN 978-3-95977-214-3, LIPICS Vol. 212 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 36 MB)
Search Publication Server

Authors
  • Ahn, Hee-Kap
  • Alanko, Jarno
  • Albers, Susanne
  • Allender, Eric
  • Anders, Markus
  • An, Hyung-Chan
  • An, Shinwoo
  • Antoniadis, Antonios
  • Araujo, Eloi
  • Aronov, Boris
  • Asano, Takao
  • Aurenhammer, Franz
  • Bacic, Joyce
  • Bandyapadhyay, Sayan
  • Banik, Aritra
  • Bar-Noy, Amotz
  • Barr, Sam
  • Barth, Florian
  • Bhore, Sujoy
  • Biabani, Leyla
  • Biedl, Therese
  • Biniaz, Ahmad
  • Black, Mitchell
  • Bläsius, Thomas
  • Bose, Prosenjit
  • Brachter, Jendrik
  • Brause, Christoph
  • Canonne, Clément L.
  • Cardinal, Jean
  • Cazaux, Bastien
  • Charalampopoulos, Panagiotis
  • Cheng, Siu-Wing
  • Chen, Ho-Lin
  • Chen, Huiping
  • Chen, Jianer
  • Cheriyan, Joseph
  • Cho, Kyungjin
  • Christen, Peter
  • Cummings, Robert
  • Czygrinow, Andrzej
  • Czyzowicz, Jurek
  • Das, Rathish
  • de Berg, Mark
  • de Berg, Sarita
  • Dippel, Jack
  • Enoch, Julian
  • Equi, Massimo
  • Eskandari, Marzieh
  • Evald, Jacob
  • Ezra, Esther
  • Fekete, Sándor P.
  • Ferragina, Paolo
  • Fox, Kyle
  • Francis, Mathew C.
  • Fredslund-Hansen, Viktor
  • Friedrich, Tobias
  • Funke, Stefan
  • Gálvez, Waldo
  • Gibson-Lopez, Matt
  • Golovach, Petr
  • Gourvès, Laurent
  • Gouwar, John
  • Gualà, Luciano
  • Gudmundsson, Joachim
  • Gupta, Siddharth
  • Gu, Qian-Ping
  • Hanćkowiak, Michał
  • Harutyunyan, Ararat
  • Hasegawa, Atsuya
  • Hébert-Johnson, Úrsula
  • Hell, Pavol
  • Hirahara, Shuichi
  • Huang, Hongyao
  • Huang, Qin
  • Iacono, John
  • Iwama, Kazuo
  • Jacob, Dalu
  • Jain, Rahul
  • Janke, Maximilian
  • Kanj, Iyad
  • Kaufman, Tali
  • Keldenich, Phillip
  • Khare, Bhavika
  • Killick, Ryan
  • Kim, Donggyu
  • Kisfaludi-Bak, Sándor
  • Klimenko, Georgiy
  • Koana, Tomohiro
  • Komusiewicz, Christian
  • Kosfeld, Ramin
  • Kranakis, Evangelos
  • Krejca, Martin S.
  • Krizanc, Danny
  • Kumabe, Soh
  • Kumar, Gunjan
  • Kumar, Nikhil
  • Kumar, Nirman
  • Lai, Kuan-Yun
  • Lampis, Michael
  • Lee, Duksang
  • Le Gall, François
  • Leucci, Stefano
  • Liang, JiaJian
  • Liang, Ya-Chun
  • Li, Guangping
  • Lincoln, Andrea
  • Li, Qian
  • Li, Shibo
  • Loukides, Grigorios
  • Lynch, Jayson
  • Maheshwari, Anil
  • Mäkinen, Veli
  • Małafiejska, Anna
  • Małafiejski, Michał
  • Manzini, Giovanni
  • Martin, Barnaby
  • Martinez, Fábio V.
  • Mass, David
  • Matheny, Michael
  • Mathieu, Claire
  • Maxwell, William
  • Mehrabi, Saeed
  • Melissinos, Nikolaos
  • Mesica, Dor
  • Mestre, Julián
  • Mitsou, Valia
  • Miyamoto, Masayuki
  • Molitor, Louise
  • Monemizadeh, Morteza
  • Mozes, Shay
  • Munro, J. Ian
  • Narayanan, Lata
  • Nikoletseas, Sotiris
  • Nilsson, Bengt J.
  • Nöllenburg, Martin
  • Norri, Tuukka
  • Ocetkiewicz, Krzysztof M.
  • Oh, Eunjin
  • Opatrny, Jaroslav
  • Orden, David
  • Oum, Sang-il
  • Palios, Leonidas
  • Pankratov, Denis
  • Papadopoulou, Evanthia
  • Pastuszak, Krzysztof
  • Patel, Dhrumil
  • Paulusma, Daniël
  • Peleg, David
  • Phillips, Jeff M.
  • Pisanti, Nadia
  • Pissis, Solon P.
  • Proissl, Claudius
  • Pupyrev, Sergey
  • Radoszewski, Jakub
  • Raichel, Benjamin
  • Raman, Rajiv
  • Raptopoulos, Christoforos
  • Rawitz, Dror
  • Ray, Saurabh
  • Rieck, Christian
  • Robelle, Caleb
  • Rozante, Luiz C.
  • Rubert, Diego P.
  • Rutter, Ignaz
  • Sa'ar, Guy
  • Sadakane, Kunihiko
  • Scheder, Dominik
  • Scheffer, Christian
  • Schnider, Patrick
  • Schweitzer, Pascal
  • Seara, Carlos
  • Shah, Rahul
  • Sharir, Micha
  • Sha, Yuan
  • Shende, Sunil
  • Shin, Yongho
  • Smid, Michiel
  • Smith, Siani
  • Sommer, Frank
  • Sonar, Chinmay
  • Spirakis, Paul
  • Staals, Frank
  • Starikovskaya, Tatiana
  • Suderland, Martin
  • Surianarayanan, Vaishali
  • Suri, Subhash
  • Tang, Shaojie
  • Tan, Shuhao
  • Theocharous, Leonidas
  • Tomescu, Alexandru I.
  • Touitou, Noam
  • Umboh, Seeun William
  • Vinciguerra, Giorgio
  • Wimmer, Karl
  • Witkowski, Marcin
  • Wong, Man Ting
  • Wu, Hsiang-Yun
  • Wulff-Nilsen, Christian
  • Xia, Ge
  • Yang, Zhongxiu
  • Yao, Fan
  • Yehezkel, Elad
  • Yokoi, Yu
  • Yuan, Jing
  • Zehavi, Meirav
  • Zhou, Hang
  • Zhu, Jasper
  • Ziccardi, Isabella
  • Żyliński, Paweł
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Ahn, Hee-Kap ; Sadakane, Kunihiko

    Abstract | Document (486 KB) | BibTeX

    Streaming Pattern Matching (Invited Talk)
    Authors: Starikovskaya, Tatiana

    Abstract | Document (264 KB) | BibTeX

    Spanning Properties of Variants of the Delaunay Graph (Invited Talk)
    Authors: Bose, Prosenjit

    Abstract | Document (280 KB) | BibTeX

    Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model
    Authors: Aronov, Boris ; de Berg, Mark ; Cardinal, Jean ; Ezra, Esther ; Iacono, John ; Sharir, Micha

    Abstract | Document (742 KB) | BibTeX

    Approximate Maximum Halfspace Discrepancy
    Authors: Matheny, Michael ; Phillips, Jeff M.

    Abstract | Document (1,238 KB) | BibTeX

    The VC-Dimension of Limited Visibility Terrains
    Authors: Gibson-Lopez, Matt ; Yang, Zhongxiu

    Abstract | Document (1,188 KB) | BibTeX

    Clustering with Neighborhoods
    Authors: Huang, Hongyao ; Klimenko, Georgiy ; Raichel, Benjamin

    Abstract | Document (780 KB) | BibTeX

    Approximating Longest Spanning Tree with Neighborhoods
    Authors: Biniaz, Ahmad

    Abstract | Document (803 KB) | BibTeX

    Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions
    Authors: Cheng, Siu-Wing ; Wong, Man Ting

    Abstract | Document (797 KB) | BibTeX

    Connected Coordinated Motion Planning with Bounded Stretch
    Authors: Fekete, Sándor P. ; Keldenich, Phillip ; Kosfeld, Ramin ; Rieck, Christian ; Scheffer, Christian

    Abstract | Document (11,807 KB) | BibTeX

    Enclosing Depth and Other Depth Measures
    Authors: Schnider, Patrick

    Abstract | Document (843 KB) | BibTeX

    Illuminating the x-Axis by α-Floodlights
    Authors: Nilsson, Bengt J. ; Orden, David ; Palios, Leonidas ; Seara, Carlos ; Żyliński, Paweł

    Abstract | Document (1,145 KB) | BibTeX

    On Geometric Priority Set Cover Problems
    Authors: Banik, Aritra ; Raman, Rajiv ; Ray, Saurabh

    Abstract | Document (710 KB) | BibTeX

    The Complexity of Sharing a Pizza
    Authors: Schnider, Patrick

    Abstract | Document (826 KB) | BibTeX

    Dynamic Data Structures for k-Nearest Neighbor Queries
    Authors: de Berg, Sarita ; Staals, Frank

    Abstract | Document (820 KB) | BibTeX

    Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets
    Authors: Barth, Florian ; Funke, Stefan ; Proissl, Claudius

    Abstract | Document (584 KB) | BibTeX

    Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest
    Authors: Barr, Sam ; Biedl, Therese

    Abstract | Document (877 KB) | BibTeX

    On the Kernel and Related Problems in Interval Digraphs
    Authors: Francis, Mathew C. ; Hell, Pavol ; Jacob, Dalu

    Abstract | Document (704 KB) | BibTeX

    Interval Query Problem on Cube-Free Median Graphs
    Authors: Kumabe, Soh

    Abstract | Document (757 KB) | BibTeX

    Untangling Circular Drawings: Algorithms and Complexity
    Authors: Bhore, Sujoy ; Li, Guangping ; Nöllenburg, Martin ; Rutter, Ignaz ; Wu, Hsiang-Yun

    Abstract | Document (1,229 KB) | BibTeX

    Algorithms and Complexity on Indexing Elastic Founder Graphs
    Authors: Equi, Massimo ; Norri, Tuukka ; Alanko, Jarno ; Cazaux, Bastien ; Tomescu, Alexandru I. ; Mäkinen, Veli

    Abstract | Document (1,299 KB) | BibTeX

    Partitioning H-Free Graphs of Bounded Diameter
    Authors: Brause, Christoph ; Golovach, Petr ; Martin, Barnaby ; Paulusma, Daniël ; Smith, Siani

    Abstract | Document (719 KB) | BibTeX

    Clique-Based Separators for Geometric Intersection Graphs
    Authors: de Berg, Mark ; Kisfaludi-Bak, Sándor ; Monemizadeh, Morteza ; Theocharous, Leonidas

    Abstract | Document (992 KB) | BibTeX

    Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs
    Authors: Evald, Jacob ; Fredslund-Hansen, Viktor ; Wulff-Nilsen, Christian

    Abstract | Document (1,182 KB) | BibTeX

    A Characterization of Individualization-Refinement Trees
    Authors: Anders, Markus ; Brachter, Jendrik ; Schweitzer, Pascal

    Abstract | Document (614 KB) | BibTeX

    Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs
    Authors: Fredslund-Hansen, Viktor ; Mozes, Shay ; Wulff-Nilsen, Christian

    Abstract | Document (826 KB) | BibTeX

    Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
    Authors: Małafiejska, Anna ; Małafiejski, Michał ; Ocetkiewicz, Krzysztof M. ; Pastuszak, Krzysztof

    Abstract | Document (705 KB) | BibTeX

    Selected Neighbor Degree Forest Realization
    Authors: Bar-Noy, Amotz ; Peleg, David ; Rawitz, Dror ; Yehezkel, Elad

    Abstract | Document (774 KB) | BibTeX

    MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems
    Authors: Nikoletseas, Sotiris ; Raptopoulos, Christoforos ; Spirakis, Paul

    Abstract | Document (908 KB) | BibTeX

    The Impact of Geometry on Monochrome Regions in the Flip Schelling Process
    Authors: Bläsius, Thomas ; Friedrich, Tobias ; Krejca, Martin S. ; Molitor, Louise

    Abstract | Document (843 KB) | BibTeX

    Piecewise-Linear Farthest-Site Voronoi Diagrams
    Authors: Aurenhammer, Franz ; Papadopoulou, Evanthia ; Suderland, Martin

    Abstract | Document (776 KB) | BibTeX

    Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm
    Authors: Black, Mitchell ; Maxwell, William

    Abstract | Document (889 KB) | BibTeX

    Anonymity-Preserving Space Partitions
    Authors: Hébert-Johnson, Úrsula ; Sonar, Chinmay ; Suri, Subhash ; Surianarayanan, Vaishali

    Abstract | Document (730 KB) | BibTeX

    Impatient PPSZ - A Faster Algorithm for CSP
    Authors: Li, Shibo ; Scheder, Dominik

    Abstract | Document (991 KB) | BibTeX

    Fine-Grained Meta-Theorems for Vertex Integrity
    Authors: Lampis, Michael ; Mitsou, Valia

    Abstract | Document (788 KB) | BibTeX

    Essentially Tight Kernels For (Weakly) Closed Graphs
    Authors: Koana, Tomohiro ; Komusiewicz, Christian ; Sommer, Frank

    Abstract | Document (809 KB) | BibTeX

    Filling Crosswords Is Very Hard
    Authors: Gourvès, Laurent ; Harutyunyan, Ararat ; Lampis, Michael ; Melissinos, Nikolaos

    Abstract | Document (778 KB) | BibTeX

    Grid Recognition: Classical and Parameterized Computational Perspectives
    Authors: Gupta, Siddharth ; Sa'ar, Guy ; Zehavi, Meirav

    Abstract | Document (1,165 KB) | BibTeX

    An Improved Approximation Algorithm for the Matching Augmentation Problem
    Authors: Cheriyan, Joseph ; Cummings, Robert ; Dippel, Jack ; Zhu, Jasper

    Abstract | Document (739 KB) | BibTeX

    Multimodal Transportation with Ridesharing of Personal Vehicles
    Authors: Gu, Qian-Ping ; Liang, JiaJian

    Abstract | Document (6,646 KB) | BibTeX

    Algorithms for Normalized Multiple Sequence Alignments
    Authors: Araujo, Eloi ; Rozante, Luiz C. ; Rubert, Diego P. ; Martinez, Fábio V.

    Abstract | Document (980 KB) | BibTeX

    Separated Red Blue Center Clustering
    Authors: Eskandari, Marzieh ; Khare, Bhavika ; Kumar, Nirman

    Abstract | Document (777 KB) | BibTeX

    On the Extended TSP Problem
    Authors: Mestre, Julián ; Pupyrev, Sergey ; Umboh, Seeun William

    Abstract | Document (741 KB) | BibTeX

    Probabilistic Analysis of Euclidean Capacitated Vehicle Routing
    Authors: Mathieu, Claire ; Zhou, Hang

    Abstract | Document (824 KB) | BibTeX

    Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane
    Authors: Bandyapadhyay, Sayan ; Maheshwari, Anil ; Smid, Michiel

    Abstract | Document (730 KB) | BibTeX

    Augmenting Graphs to Minimize the Radius
    Authors: Gudmundsson, Joachim ; Sha, Yuan ; Yao, Fan

    Abstract | Document (1,164 KB) | BibTeX

    Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces
    Authors: Cho, Kyungjin ; Oh, Eunjin

    Abstract | Document (827 KB) | BibTeX

    Feedback Vertex Set on Geometric Intersection Graphs
    Authors: An, Shinwoo ; Oh, Eunjin

    Abstract | Document (760 KB) | BibTeX

    Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time
    Authors: Chen, Jianer ; Huang, Qin ; Kanj, Iyad ; Li, Qian ; Xia, Ge

    Abstract | Document (851 KB) | BibTeX

    Making Three out of Two: Three-Way Online Correlated Selection
    Authors: Shin, Yongho ; An, Hyung-Chan

    Abstract | Document (801 KB) | BibTeX

    Tight Competitive Analyses of Online Car-Sharing Problems
    Authors: Liang, Ya-Chun ; Lai, Kuan-Yun ; Chen, Ho-Lin ; Iwama, Kazuo

    Abstract | Document (606 KB) | BibTeX

    Skeletons and Minimum Energy Scheduling
    Authors: Antoniadis, Antonios ; Kumar, Gunjan ; Kumar, Nikhil

    Abstract | Document (789 KB) | BibTeX

    Machine Covering in the Random-Order Model
    Authors: Albers, Susanne ; Gálvez, Waldo ; Janke, Maximilian

    Abstract | Document (808 KB) | BibTeX

    Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay
    Authors: Touitou, Noam

    Abstract | Document (762 KB) | BibTeX

    Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity
    Authors: Allender, Eric ; Gouwar, John ; Hirahara, Shuichi ; Robelle, Caleb

    Abstract | Document (914 KB) | BibTeX

    Identity Testing Under Label Mismatch
    Authors: Canonne, Clément L. ; Wimmer, Karl

    Abstract | Document (800 KB) | BibTeX

    Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion
    Authors: Kaufman, Tali ; Mass, David

    Abstract | Document (685 KB) | BibTeX

    Group Evacuation on a Line by Agents with Different Communication Abilities
    Authors: Czyzowicz, Jurek ; Killick, Ryan ; Kranakis, Evangelos ; Krizanc, Danny ; Narayanan, Lata ; Opatrny, Jaroslav ; Pankratov, Denis ; Shende, Sunil

    Abstract | Document (766 KB) | BibTeX

    Lower Bounds for Induced Cycle Detection in Distributed Computing
    Authors: Le Gall, François ; Miyamoto, Masayuki

    Abstract | Document (915 KB) | BibTeX

    Distributed Approximations of f-Matchings and b-Matchings in Graphs of Sub-Logarithmic Expansion
    Authors: Czygrinow, Andrzej ; Hanćkowiak, Michał ; Witkowski, Marcin

    Abstract | Document (725 KB) | BibTeX

    Inverse Suffix Array Queries for 2-Dimensional Pattern Matching in Near-Compact Space
    Authors: Patel, Dhrumil ; Shah, Rahul

    Abstract | Document (966 KB) | BibTeX

    Dynamic Boolean Formula Evaluation
    Authors: Das, Rathish ; Lincoln, Andrea ; Lynch, Jayson ; Munro, J. Ian

    Abstract | Document (734 KB) | BibTeX

    Shortest Beer Path Queries in Outerplanar Graphs
    Authors: Bacic, Joyce ; Mehrabi, Saeed ; Smid, Michiel

    Abstract | Document (890 KB) | BibTeX

    Space-Efficient Algorithms for Reachability in Directed Geometric Graphs
    Authors: Bhore, Sujoy ; Jain, Rahul

    Abstract | Document (1,015 KB) | BibTeX

    Repetition- and Linearity-Aware Rank/Select Dictionaries
    Authors: Ferragina, Paolo ; Manzini, Giovanni ; Vinciguerra, Giorgio

    Abstract | Document (961 KB) | BibTeX

    Pattern Masking for Dictionary Matching
    Authors: Charalampopoulos, Panagiotis ; Chen, Huiping ; Christen, Peter ; Loukides, Grigorios ; Pisanti, Nadia ; Pissis, Solon P. ; Radoszewski, Jakub

    Abstract | Document (1,360 KB) | BibTeX

    Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees
    Authors: Gualà, Luciano ; Leucci, Stefano ; Ziccardi, Isabella

    Abstract | Document (1,036 KB) | BibTeX

    Computing Shapley Values for Mean Width in 3-D
    Authors: Tan, Shuhao

    Abstract | Document (807 KB) | BibTeX

    Simple Envy-Free and Truthful Mechanisms for Cake Cutting with a Small Number of Cuts
    Authors: Asano, Takao

    Abstract | Document (768 KB) | BibTeX

    Adaptive Regularized Submodular Maximization
    Authors: Tang, Shaojie ; Yuan, Jing

    Abstract | Document (669 KB) | BibTeX

    Γ-Graphic Delta-Matroids and Their Applications
    Authors: Kim, Donggyu ; Lee, Duksang ; Oum, Sang-il

    Abstract | Document (759 KB) | BibTeX

    An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints
    Authors: Yokoi, Yu

    Abstract | Document (781 KB) | BibTeX

    A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities
    Authors: Enoch, Julian ; Fox, Kyle ; Mesica, Dor ; Mozes, Shay

    Abstract | Document (861 KB) | BibTeX

    Maximum-Weight Matching in Sliding Windows and Beyond
    Authors: Biabani, Leyla ; de Berg, Mark ; Monemizadeh, Morteza

    Abstract | Document (741 KB) | BibTeX

    Quantum Advantage with Shallow Circuits Under Arbitrary Corruption
    Authors: Hasegawa, Atsuya ; Le Gall, François

    Abstract | Document (1,109 KB) | BibTeX

    		  



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