Portal - ISAAC 2021

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

Charalampopoulos, Panagiotis

Fredslund-Hansen, Viktor

Hébert-Johnson, Úrsula

Kisfaludi-Bak, Sándor

Klimenko, Georgiy

Koana, Tomohiro

Komusiewicz, Christian

Ocetkiewicz, Krzysztof M.

Papadopoulou, Evanthia

Raptopoulos, Christoforos

Starikovskaya, Tatiana

Suderland, Martin

Suri, Subhash

Surianarayanan, Vaishali

Tan, Shuhao

Tang, Shaojie

Theocharous, Leonidas

Tomescu, Alexandru I.

Wulff-Nilsen, Christian

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

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