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
  • Agrawal, Anadi
  • Ahn, Jungho
  • Alcock, Leo
  • Amir, Amihood
  • An, Hyung-Chan
  • Aronov, Boris
  • Asano, Takao
  • Asif, Sualeh
  • Bartier, Valentin
  • Bellitto, Thomas
  • Bentert, Matthias
  • Bérczi, Kristóf
  • Bhaskar, Umang
  • Bille, Philip
  • Boneh, Itai
  • Bosboom, Jeffrey
  • Bousquet, Nicolas
  • Bradshaw, Peter
  • Brückner, Guido
  • Brunner, Josh
  • Cantu, Angel A.
  • Cao, Yixin
  • Cardinal, Jean
  • Casteigts, Arnaud
  • Chakraborty, Dibyayan
  • Chakraborty, Sankardeep
  • Chen, Charlotte
  • Cheng, Siu-Wing
  • Chen, Hubie
  • Chen, Ke
  • Chia, Nai-Hui
  • Cho, Hwan-Gue
  • Dallard, Clément
  • Das, Sandip
  • de Berg, Mark
  • Demaine, Erik D.
  • Dey, Sanjana
  • Dublois, Louis
  • Dudek, Bartłomiej
  • Dulęba, Maciej
  • Dumitrescu, Adrian
  • Epstein, Rogers
  • Feng, Qilong
  • Fluschnik, Till
  • Fomin, Fedor V.
  • Foucaud, Florent
  • Frei, Fabian
  • Funke, Stefan
  • Gahlawat, Harmender
  • Gawrychowski, Paweł
  • Georgiadis, Loukas
  • Ghosh, Anirban
  • Gilyén, András
  • Golovach, Petr A.
  • Gørtz, Inge Li
  • Gowda, Kishen N.
  • Gudmundsson, Joachim
  • Hamersma, Joep
  • Hanaka, Tesshu
  • Heeger, Klaus
  • Hemaspaandra, Edith
  • He, Meng
  • Hendrickson, Dylan
  • Hesterberg, Adam
  • Himmel, Anne-Sophie
  • Hirschfeld, Lior
  • Holland, William L.
  • Huang, Xuangui
  • Huang, Ziyun
  • Hu, William
  • Hyatt-Denesik, Dylan
  • Inenaga, Shunsuke
  • Ito, Takehiro
  • Jaffke, Lars
  • Janczewski, Wojciech
  • Jansen, Bart M. P.
  • Joffard, Alice
  • Kakimura, Naonori
  • Kern, Walter
  • Khosravian Ghadikolaei, Mehdi
  • Kim, Eun Jung
  • Kim, Kangsan
  • Kim, Sung-Hwan
  • Knop, Dušan
  • Koana, Tomohiro
  • Kobayashi, Yusuke
  • Komusiewicz, Christian
  • Kopinsky, Justin
  • Kosinas, Evangelos
  • Koutecký, Martin
  • Krnetić, Predrag
  • Kumar, Gunjan
  • Kumar, Nikhil
  • Labarre, Anthony
  • Lajou, Dimitri
  • Lampis, Michael
  • Lee, Euiwoong
  • Li, Minming
  • Lin, Han-Hsuan
  • Li, Shaohua
  • Lloyd, Seth
  • Lomer, Kyle
  • Lonkar, Aditya
  • Luchsinger, Austin
  • Lynch, Jayson
  • Markovic, Aleksandar
  • Masařk, Tomáš
  • Melissinos, Nikolaos
  • Melnyk, Darya
  • Miltzow, Tillmann
  • Molter, Hendrik
  • Montealegre, Pedro
  • Mouawad, Amer E.
  • Mulzer, Wolfgang
  • Munro, J. Ian
  • Nandy, Subhas C.
  • Nekrich, Yakov
  • Nguyen, Trung Thanh
  • Niedermeier, Rolf
  • Oh, Eunjin
  • Okrasa, Karolina
  • Onodera, Taku
  • Ophelders, Tim
  • Oum, Sang-il
  • Ouvrard, Paul
  • Pang, Haozhou
  • Panolan, Fahad
  • Patel, Vraj
  • Paulusma, Daniël
  • Philip, Geevarghese
  • Pieterse, Astrid
  • Pilipczuk, Marcin
  • Rahgoshay, Mirmahdi
  • Ramírez-Romero, Diego
  • Rapaport, Ivan
  • Rothe, Jörg
  • Roy, Bodhayan
  • Rutter, Ignaz
  • Rzążewski, Paweł
  • Sadakane, Kunihiko
  • Sagunov, Danil
  • Sakai, Yoshifumi
  • Salavatipour, Mohammad R.
  • Santiago, Richard
  • Satti, Srinivasa Rao
  • Saurabh, Saket
  • Scheffler, Sarah
  • Schubert, Carsten
  • Schweller, Robert
  • Sen, Arunabha
  • Sha, Yuan
  • Shibuya, Tetsuo
  • Shin, Yongho
  • Sommer, Frank
  • Sonke, Willem
  • Sorge, Manuel
  • Stacho, Ladislav
  • Sumigawa, Kentaro
  • Tamura, Yuma
  • Tang, Ewin
  • Thắng, Nguyễn Kim
  • Tóth, Csaba D.
  • Uchizawa, Kei
  • Umboh, Seeun William
  • Umeda, Hiroyuki
  • Uno, Yushi
  • van der Zanden, Tom C.
  • van Kreveld, Marc
  • Vermeulen, Jordi L.
  • Wang, Chunhao
  • Wang, Jianxin
  • Wang, Yuyi
  • Wattenhofer, Roger
  • Weitbrecht, Felix
  • Wellman, Julian
  • Wild, Sebastian
  • Willert, Max
  • Wirth, Anthony
  • Wong, Sampson
  • Wu, Kaiyu
  • Wylie, Tim
  • Xu, Jinhui
  • Yi, Ke
  • Yoshida, Yuichi
  • Zhang, Lillian
  • Zhang, Zhen
  • Zhou, Xiao
  • Zink, Johannes
  • Zobel, Justin
  • Zschoche, Philipp

  •   
    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