Portal - ISAAC 2020

ISAAC 2020	December 14-18, 2020, Hong Kong, China (Virtual Conference)
31st International Symposium on Algorithms and Computation (ISAAC 2020) Yixin Cao and Siu-Wing Cheng and Minming Li (Eds.)
ISBN 978-3-95977-173-3, LIPICS Vol. 181	ISSN 1868-8969

Additional Information

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

Authors

Chakraborty, Dibyayan

Chakraborty, Sankardeep

Khosravian Ghadikolaei, Mehdi

Komusiewicz, Christian

Ramírez-Romero, Diego

Salavatipour, Mohammad R.

van der Zanden, Tom C.

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Cao, Yixin ; Cheng, Siu-Wing ; Li, Minming

Abstract | Document (297 KB) | BibTeX

How to Decompose a Graph into a Tree-Like Structure (Invited Talk)

Authors: Oum, Sang-il

Abstract | Document (156 KB) | BibTeX

Worst-Case Optimal Join Algorithms (Invited Talk)

Authors: Yi, Ke

Abstract | Document (155 KB) | BibTeX

(In)approximability of Maximum Minimal FVS

Authors: Dublois, Louis ; Hanaka, Tesshu ; Khosravian Ghadikolaei, Mehdi ; Lampis, Michael ; Melissinos, Nikolaos

Abstract | Document (1,713 KB) | BibTeX

A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem

Authors: Agrawal, Anadi ; Gawrychowski, Paweł

Abstract | Document (446 KB) | BibTeX

A Unified Framework of FPT Approximation Algorithms for Clustering Problems

Authors: Feng, Qilong ; Zhang, Zhen ; Huang, Ziyun ; Xu, Jinhui ; Wang, Jianxin

Abstract | Document (549 KB) | BibTeX

A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length

Authors: Sakai, Yoshifumi ; Inenaga, Shunsuke

Abstract | Document (603 KB) | BibTeX

Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs

Authors: Chakraborty, Dibyayan ; Das, Sandip ; Foucaud, Florent ; Gahlawat, Harmender ; Lajou, Dimitri ; Roy, Bodhayan

Abstract | Document (631 KB) | BibTeX

An SPQR-Tree-Like Embedding Representation for Level Planarity

Authors: Brückner, Guido ; Rutter, Ignaz

Abstract | Document (699 KB) | BibTeX

Approximating the Packedness of Polygonal Curves

Authors: Gudmundsson, Joachim ; Sha, Yuan ; Wong, Sampson

Abstract | Document (660 KB) | BibTeX

Approximation Algorithms for Generalized Path Scheduling

Authors: Pang, Haozhou ; Salavatipour, Mohammad R.

Abstract | Document (547 KB) | BibTeX

Approximations for Throughput Maximization

Authors: Hyatt-Denesik, Dylan ; Rahgoshay, Mirmahdi ; Salavatipour, Mohammad R.

Abstract | Document (550 KB) | BibTeX

Arithmetic Expression Construction

Authors: Alcock, Leo ; Asif, Sualeh ; Bosboom, Jeffrey ; Brunner, Josh ; Chen, Charlotte ; Demaine, Erik D. ; Epstein, Rogers ; Hesterberg, Adam ; Hirschfeld, Lior ; Hu, William ; Lynch, Jayson ; Scheffler, Sarah ; Zhang, Lillian

Abstract | Document (584 KB) | BibTeX

Between Shapes, Using the Hausdorff Distance

Authors: van Kreveld, Marc ; Miltzow, Tillmann ; Ophelders, Tim ; Sonke, Willem ; Vermeulen, Jordi L.

Abstract | Document (867 KB) | BibTeX

Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs

Authors: Nguyen, Trung Thanh ; Rothe, Jörg

Abstract | Document (615 KB) | BibTeX

Cake Cutting: An Envy-Free and Truthful Mechanism with a Small Number of Cuts

Authors: Asano, Takao ; Umeda, Hiroyuki

Abstract | Document (570 KB) | BibTeX

Compact Routing in Unit Disk Graphs

Authors: Mulzer, Wolfgang ; Willert, Max

Abstract | Document (586 KB) | BibTeX

Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard

Authors: Brunner, Josh ; Demaine, Erik D. ; Hendrickson, Dylan ; Wellman, Julian

Abstract | Document (744 KB) | BibTeX

Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines

Authors: Koutecký, Martin ; Zink, Johannes

Abstract | Document (708 KB) | BibTeX

Complexity of Stability

Authors: Frei, Fabian ; Hemaspaandra, Edith ; Rothe, Jörg

Abstract | Document (483 KB) | BibTeX

Computing Dense and Sparse Subgraphs of Weakly Closed Graphs

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

Abstract | Document (561 KB) | BibTeX

Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem

Authors: Kim, Kangsan ; Shin, Yongho ; An, Hyung-Chan

Abstract | Document (562 KB) | BibTeX

Contracting to a Longest Path in H-Free Graphs

Authors: Kern, Walter ; Paulusma, Daniël

Abstract | Document (720 KB) | BibTeX

Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs

Authors: Dudek, Bartłomiej ; Gawrychowski, Paweł

Abstract | Document (645 KB) | BibTeX

Discriminating Codes in Geometric Setups

Authors: Dey, Sanjana ; Foucaud, Florent ; Nandy, Subhas C. ; Sen, Arunabha

Abstract | Document (846 KB) | BibTeX

Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees

Authors: He, Meng ; Munro, J. Ian ; Nekrich, Yakov ; Wild, Sebastian ; Wu, Kaiyu

Abstract | Document (784 KB) | BibTeX

Diverse Pairs of Matchings

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Jaffke, Lars ; Philip, Geevarghese ; Sagunov, Danil

Abstract | Document (569 KB) | BibTeX

Efficient Labeling for Reachability in Directed Acyclic Graphs

Authors: Dulęba, Maciej ; Gawrychowski, Paweł ; Janczewski, Wojciech

Abstract | Document (566 KB) | BibTeX

Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences

Authors: Funke, Stefan ; Weitbrecht, Felix

Abstract | Document (788 KB) | BibTeX

Enumerating Range Modes

Authors: Sumigawa, Kentaro ; Chakraborty, Sankardeep ; Sadakane, Kunihiko ; Satti, Srinivasa Rao

Abstract | Document (1,195 KB) | BibTeX

Finding Temporal Paths Under Waiting Time Constraints

Authors: Casteigts, Arnaud ; Himmel, Anne-Sophie ; Molter, Hendrik ; Zschoche, Philipp

Abstract | Document (642 KB) | BibTeX

Flexible List Colorings in Graphs with Special Degeneracy Conditions

Authors: Bradshaw, Peter ; Masařk, Tomáš ; Stacho, Ladislav

Abstract | Document (474 KB) | BibTeX

Geometric Pattern Matching Reduces to k-SUM

Authors: Aronov, Boris ; Cardinal, Jean

Abstract | Document (466 KB) | BibTeX

Gourds: A Sliding-Block Puzzle with Turning

Authors: Hamersma, Joep ; van Kreveld, Marc ; Uno, Yushi ; van der Zanden, Tom C.

Abstract | Document (1,990 KB) | BibTeX

Improved FPT Algorithms for Deletion to Forest-Like Structures

Authors: Gowda, Kishen N. ; Lonkar, Aditya ; Panolan, Fahad ; Patel, Vraj ; Saurabh, Saket

Abstract | Document (658 KB) | BibTeX

Indexing Isodirectional Pointer Sequences

Authors: Kim, Sung-Hwan ; Cho, Hwan-Gue

Abstract | Document (1,838 KB) | BibTeX

Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters

Authors: Bentert, Matthias ; Heeger, Klaus ; Knop, Dušan

Abstract | Document (593 KB) | BibTeX

Linear Transformations Between Dominating Sets in the TAR-Model

Authors: Bousquet, Nicolas ; Joffard, Alice ; Ouvrard, Paul

Abstract | Document (590 KB) | BibTeX

Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems

Authors: Georgiadis, Loukas ; Kosinas, Evangelos

Abstract | Document (637 KB) | BibTeX

Market Pricing for Matroid Rank Valuations

Authors: Bérczi, Kristóf ; Kakimura, Naonori ; Kobayashi, Yusuke

Abstract | Document (463 KB) | BibTeX

Minimization and Parameterized Variants of Vertex Partition Problems on Graphs

Authors: Tamura, Yuma ; Ito, Takehiro ; Zhou, Xiao

Abstract | Document (646 KB) | BibTeX

Multicommodity Flows in Planar Graphs with Demands on Faces

Authors: Kumar, Nikhil

Abstract | Document (756 KB) | BibTeX

Multiparty Selection

Authors: Chen, Ke ; Dumitrescu, Adrian

Abstract | Document (498 KB) | BibTeX

Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs

Authors: Fluschnik, Till ; Niedermeier, Rolf ; Schubert, Carsten ; Zschoche, Philipp

Abstract | Document (565 KB) | BibTeX

On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Authors: Bartier, Valentin ; Bousquet, Nicolas ; Dallard, Clément ; Lomer, Kyle ; Mouawad, Amer E.

Abstract | Document (714 KB) | BibTeX

Online Primal-Dual Algorithms with Configuration Linear Programs

Authors: Thắng, Nguyễn Kim

Abstract | Document (545 KB) | BibTeX

Partial Function Extension with Applications to Learning and Property Testing

Authors: Bhaskar, Umang ; Kumar, Gunjan

Abstract | Document (487 KB) | BibTeX

Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension

Authors: Chia, Nai-Hui ; Gilyén, András ; Lin, Han-Hsuan ; Lloyd, Seth ; Tang, Ewin ; Wang, Chunhao

Abstract | Document (561 KB) | BibTeX

Random Access in Persistent Strings

Authors: Bille, Philip ; Gørtz, Inge Li

Abstract | Document (2,867 KB) | BibTeX

Recency Queries with Succinct Representation

Authors: Holland, William L. ; Wirth, Anthony ; Zobel, Justin

Abstract | Document (550 KB) | BibTeX

Recursed Is Not Recursive: A Jarring Result

Authors: Demaine, Erik D. ; Kopinsky, Justin ; Lynch, Jayson

Abstract | Document (1,174 KB) | BibTeX

Shared vs Private Randomness in Distributed Interactive Proofs

Authors: Montealegre, Pedro ; Ramírez-Romero, Diego ; Rapaport, Ivan

Abstract | Document (586 KB) | BibTeX

Shortest-Path Queries in Geometric Networks

Authors: Oh, Eunjin

Abstract | Document (575 KB) | BibTeX

Signal Passing Self-Assembly Simulates Tile Automata

Authors: Cantu, Angel A. ; Luchsinger, Austin ; Schweller, Robert ; Wylie, Tim

Abstract | Document (1,067 KB) | BibTeX

Size, Depth and Energy of Threshold Circuits Computing Parity Function

Authors: Uchizawa, Kei

Abstract | Document (459 KB) | BibTeX

Sorting by Prefix Block-Interchanges

Authors: Labarre, Anthony

Abstract | Document (540 KB) | BibTeX

Space Hardness of Solving Structured Linear Systems

Authors: Huang, Xuangui

Abstract | Document (613 KB) | BibTeX

Sparse Hop Spanners for Unit Disk Graphs

Authors: Dumitrescu, Adrian ; Ghosh, Anirban ; Tóth, Csaba D.

Abstract | Document (719 KB) | BibTeX

Sparsification Lower Bounds for List H-Coloring

Authors: Chen, Hubie ; Jansen, Bart M. P. ; Okrasa, Karolina ; Pieterse, Astrid ; Rzążewski, Paweł

Abstract | Document (782 KB) | BibTeX

The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs

Authors: Bellitto, Thomas ; Li, Shaohua ; Okrasa, Karolina ; Pilipczuk, Marcin ; Sorge, Manuel

Abstract | Document (790 KB) | BibTeX

The Online Broadcast Range-Assignment Problem

Authors: de Berg, Mark ; Markovic, Aleksandar ; Umboh, Seeun William

Abstract | Document (554 KB) | BibTeX

The k-Server Problem with Delays on the Uniform Metric Space

Authors: Krnetić, Predrag ; Melnyk, Darya ; Wang, Yuyi ; Wattenhofer, Roger

Abstract | Document (435 KB) | BibTeX

Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion

Authors: Ahn, Jungho ; Kim, Eun Jung ; Lee, Euiwoong

Abstract | Document (624 KB) | BibTeX

Update Query Time Trade-Off for Dynamic Suffix Arrays

Authors: Amir, Amihood ; Boneh, Itai

Abstract | Document (525 KB) | BibTeX

Weakly Submodular Function Maximization Using Local Submodularity Ratio

Authors: Santiago, Richard ; Yoshida, Yuichi

Abstract | Document (557 KB) | BibTeX

Wear Leveling Revisited

Authors: Onodera, Taku ; Shibuya, Tetsuo

Abstract | Document (556 KB) | BibTeX

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

31st International Symposium on Algorithms and Computation (ISAAC 2020)