Portal - ISAAC 2022

ISAAC 2022	December 19-21, 2022, Seoul, Korea
33rd International Symposium on Algorithms and Computation (ISAAC 2022) Sang Won Bae and Heejin Park (Eds.)
ISBN 978-3-95977-258-7, LIPICS Vol. 248	ISSN 1868-8969

Additional Information

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

Authors

Chakraborty, Dibyayan

D'Angelo, Gianlorenzo

Fazekas, Szilárd Zsolt

Georgiou, Konstantinos

Gonzalez, Carolina Lucía

Naredla, Anurag Murty

Proskurin, Nikolay V.

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Bae, Sang Won ; Park, Heejin

Abstract | Document (15,907 KB) | BibTeX

Succinct Representations of Graphs (Invited Talk)

Authors: Sadakane, Kunihiko

Abstract | Document (257 KB) | BibTeX

The Tragedy of Being Almost but Not Quite Planar (Invited Talk)

Authors: Erickson, Jeff

Abstract | Document (326 KB) | BibTeX

A Local Search Algorithm for the Min-Sum Submodular Cover Problem

Authors: Hellerstein, Lisa ; Lidbetter, Thomas ; Witter, R. Teal

Abstract | Document (732 KB) | BibTeX

Algorithms for Coloring Reconfiguration Under Recolorability Digraphs

Authors: Fujii, Soichiro ; Iwamasa, Yuni ; Kimura, Kei ; Suzuki, Akira

Abstract | Document (1,217 KB) | BibTeX

Algorithms for Landmark Hub Labeling

Authors: Storandt, Sabine

Abstract | Document (648 KB) | BibTeX

An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes

Authors: Hasegawa, Atsuya ; Le Gall, François

Abstract | Document (1,176 KB) | BibTeX

Approximating the Minimum Logarithmic Arrangement Problem

Authors: Mestre, Julián ; Pupyrev, Sergey

Abstract | Document (796 KB) | BibTeX

Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP

Authors: Friggstad, Zachary ; Mousavi, Ramin

Abstract | Document (752 KB) | BibTeX

Budgeted Out-Tree Maximization with Submodular Prizes

Authors: D'Angelo, Gianlorenzo ; Delfaraz, Esmaeil ; Gilbert, Hugo

Abstract | Document (808 KB) | BibTeX

Clustering with Faulty Centers

Authors: Fox, Kyle ; Huang, Hongyao ; Raichel, Benjamin

Abstract | Document (659 KB) | BibTeX

Combinatorial and Algorithmic Aspects of Monadic Stability

Authors: Dreier, Jan ; Mählmann, Nikolas ; Mouawad, Amer E. ; Siebertz, Sebastian ; Vigny, Alexandre

Abstract | Document (868 KB) | BibTeX

Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond

Authors: Chakraborty, Dibyayan ; Dailly, Antoine ; Das, Sandip ; Foucaud, Florent ; Gahlawat, Harmender ; Ghosh, Subir Kumar

Abstract | Document (962 KB) | BibTeX

Computation of Cycle Bases in Surface Embedded Graphs

Authors: Fox, Kyle ; Stanley, Thomas

Abstract | Document (672 KB) | BibTeX

Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws

Authors: Dębski, Michał ; Lonc, Zbigniew ; Okrasa, Karolina ; Piecyk, Marta ; Rzążewski, Paweł

Abstract | Document (951 KB) | BibTeX

Computing Palindromes on a Trie in Linear Time

Authors: Mieno, Takuya ; Funakoshi, Mitsuru ; Inenaga, Shunsuke

Abstract | Document (1,420 KB) | BibTeX

Distortion-Oblivious Algorithms for Scheduling on Multiple Machines

Authors: Azar, Yossi ; Peretz, Eldad ; Touitou, Noam

Abstract | Document (725 KB) | BibTeX

Efficiently Reconfiguring a Connected Swarm of Labeled Robots

Authors: Fekete, Sándor P. ; Kramer, Peter ; Rieck, Christian ; Scheffer, Christian ; Schmidt, Arne

Abstract | Document (871 KB) | BibTeX

Entropy Matters: Understanding Performance of Sparse Random Embeddings

Authors: Skorski, Maciej

Abstract | Document (712 KB) | BibTeX

Evacuation from a Disk for Robots with Asymmetric Communication

Authors: Georgiou, Konstantinos ; Giachoudis, Nikos ; Kranakis, Evangelos

Abstract | Document (528 KB) | BibTeX

Extended MSO Model Checking via Small Vertex Integrity

Authors: Gima, Tatsuya ; Otachi, Yota

Abstract | Document (896 KB) | BibTeX

External-Memory Dictionaries with Worst-Case Update Cost

Authors: Das, Rathish ; Iacono, John ; Nekrich, Yakov

Abstract | Document (720 KB) | BibTeX

Finding Matching Cuts in H-Free Graphs

Authors: Lucke, Felicia ; Paulusma, Daniël ; Ries, Bernard

Abstract | Document (749 KB) | BibTeX

Graph Product Structure for h-Framed Graphs

Authors: Bekos, Michael A. ; Da Lozzo, Giordano ; Hliněný, Petr ; Kaufmann, Michael

Abstract | Document (1,164 KB) | BibTeX

Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy

Authors: Belova, Tatiana ; Bliznets, Ivan

Abstract | Document (731 KB) | BibTeX

Hierarchical Categories in Colored Searching

Authors: Afshani, Peyman ; Killmann, Rasmus ; Larsen, Kasper Green

Abstract | Document (623 KB) | BibTeX

How to Base Security on the Perfect/Statistical Binding Property of Quantum Bit Commitment?

Authors: Fang, Junbin ; Unruh, Dominique ; Yan, Jun ; Zhou, Dehua

Abstract | Document (587 KB) | BibTeX

Improved Compression of the Okamura-Seymour Metric

Authors: Mozes, Shay ; Wallheimer, Nathan ; Weimann, Oren

Abstract | Document (1,217 KB) | BibTeX

Improving the Bounds of the Online Dynamic Power Management Problem

Authors: Liang, Ya-Chun ; Iwama, Kazuo ; Liao, Chung-Shou

Abstract | Document (791 KB) | BibTeX

Integer Complexity and Mixed Binary-Ternary Representation

Authors: Amano, Kazuyuki

Abstract | Document (1,450 KB) | BibTeX

List Locally Surjective Homomorphisms in Hereditary Graph Classes

Authors: Dvořák, Pavel ; Masařík, Tomáš ; Novotná, Jana ; Krawczyk, Monika ; Rzążewski, Paweł ; Żuk, Aneta

Abstract | Document (1,183 KB) | BibTeX

Locally Checkable Problems Parameterized by Clique-Width

Authors: Baghirova, Narmina ; Gonzalez, Carolina Lucía ; Ries, Bernard ; Schindl, David

Abstract | Document (886 KB) | BibTeX

Lower Bounds on Retroactive Data Structures

Authors: Chung, Lily ; Demaine, Erik D. ; Hendrickson, Dylan ; Lynch, Jayson

Abstract | Document (788 KB) | BibTeX

Minimizing the Maximum Flow Time in the Online Food Delivery Problem

Authors: Guo, Xiangyu ; Luo, Kelin ; Li, Shi ; Zhang, Yuhao

Abstract | Document (901 KB) | BibTeX

Minimum Link Fencing

Authors: Bhore, Sujoy ; Klute, Fabian ; Löffler, Maarten ; Nöllenburg, Martin ; Terziadis, Soeren ; Villedieu, Anaïs

Abstract | Document (1,331 KB) | BibTeX

Multi-Robot Motion Planning for Unit Discs with Revolving Areas

Authors: Agarwal, Pankaj K. ; Geft, Tzvika ; Halperin, Dan ; Taylor, Erin

Abstract | Document (1,136 KB) | BibTeX

Nested Active-Time Scheduling

Authors: Cao, Nairen ; Fineman, Jeremy T. ; Li, Shi ; Mestre, Julián ; Russell, Katina ; Umboh, Seeun William

Abstract | Document (846 KB) | BibTeX

On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding

Authors: Fazekas, Szilárd Zsolt ; Kim, Hwee ; Matsuoka, Ryuichi ; Seki, Shinnosuke ; Takeuchi, Hinano

Abstract | Document (10,744 KB) | BibTeX

On Constrained Intersection Representations of Graphs and Digraphs

Authors: Cicalese, Ferdinando ; Dallard, Clément ; Milanič, Martin

Abstract | Document (717 KB) | BibTeX

On Finding Short Reconfiguration Sequences Between Independent Sets

Authors: Agrawal, Akanksha ; Hait, Soumita ; Mouawad, Amer E.

Abstract | Document (849 KB) | BibTeX

On Graphs Coverable by k Shortest Paths

Authors: Dumas, Maël ; Foucaud, Florent ; Perez, Anthony ; Todinca, Ioan

Abstract | Document (942 KB) | BibTeX

On Maximizing Sums of Non-Monotone Submodular and Linear Functions

Authors: Qi, Benjamin

Abstract | Document (798 KB) | BibTeX

On Reverse Shortest Paths in Geometric Proximity Graphs

Authors: Agarwal, Pankaj K. ; Katz, Matthew J. ; Sharir, Micha

Abstract | Document (1,003 KB) | BibTeX

On the Complexity of Rainbow Vertex Colouring Diametral Path Graphs

Authors: Dyrseth, Jakob ; Lima, Paloma T.

Abstract | Document (948 KB) | BibTeX

On the Complexity of Tree Edit Distance with Variables

Authors: Akutsu, Tatsuya ; Mori, Tomoya ; Nakamura, Naotoshi ; Kozawa, Satoshi ; Ueno, Yuhei ; Sato, Thomas N.

Abstract | Document (731 KB) | BibTeX

On the Cop Number of String Graphs

Authors: Das, Sandip ; Gahlawat, Harmender

Abstract | Document (926 KB) | BibTeX

On the Parameterized Intractability of Determinant Maximization

Authors: Ohsaka, Naoto

Abstract | Document (903 KB) | BibTeX

One-Face Shortest Disjoint Paths with a Deviation Terminal

Authors: Kobayashi, Yusuke ; Terao, Tatsuya

Abstract | Document (829 KB) | BibTeX

Optimizing Quantum Circuit Parameters via SDP

Authors: Lee, Eunou

Abstract | Document (660 KB) | BibTeX

Package Delivery Using Drones with Restricted Movement Areas

Authors: Erlebach, Thomas ; Luo, Kelin ; Spieksma, Frits C.R.

Abstract | Document (934 KB) | BibTeX

Parameterized Approximation Algorithms for TSP

Authors: Zhou, Jianqi ; Li, Peihua ; Guo, Jiong

Abstract | Document (720 KB) | BibTeX

Partial and Simultaneous Transitive Orientations via Modular Decompositions

Authors: Münch, Miriam ; Rutter, Ignaz ; Stumpf, Peter

Abstract | Document (983 KB) | BibTeX

Polynomial Threshold Functions for Decision Lists

Authors: Podolskii, Vladimir ; Proskurin, Nikolay V.

Abstract | Document (713 KB) | BibTeX

Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time

Authors: Lapey, Paul ; Williams, Aaron

Abstract | Document (1,552 KB) | BibTeX

Popular Edges with Critical Nodes

Authors: Chatterjee, Kushagra ; Nimbhorkar, Prajakta

Abstract | Document (708 KB) | BibTeX

Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average

Authors: Kobayashi, Yusuke ; Mahara, Ryoga

Abstract | Document (799 KB) | BibTeX

Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor

Authors: Bose, Prosenjit ; De Carufel, Jean-Lou ; Shermer, Thomas

Abstract | Document (844 KB) | BibTeX

Range Updates and Range Sum Queries on Multidimensional Points with Monoid Weights

Authors: Lu, Shangqi ; Tao, Yufei

Abstract | Document (930 KB) | BibTeX

Segment Visibility Counting Queries in Polygons

Authors: Buchin, Kevin ; Custers, Bram ; van der Hoog, Ivor ; Löffler, Maarten ; Popov, Aleksandr ; Roeloffzen, Marcel ; Staals, Frank

Abstract | Document (1,082 KB) | BibTeX

Shortest Beer Path Queries in Interval Graphs

Authors: Das, Rathish ; He, Meng ; Kondratovsky, Eitan ; Munro, J. Ian ; Naredla, Anurag Murty ; Wu, Kaiyu

Abstract | Document (885 KB) | BibTeX

Simon’s Congruence Pattern Matching

Authors: Kim, Sungmin ; Ko, Sang-Ki ; Han, Yo-Sub

Abstract | Document (817 KB) | BibTeX

Simple Order-Isomorphic Matching Index with Expected Compact Space

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

Abstract | Document (2,084 KB) | BibTeX

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings

Authors: Kammer, Frank ; Meintrup, Johannes

Abstract | Document (736 KB) | BibTeX

Subquadratic Weighted Matroid Intersection Under Rank Oracles

Authors: Tu, Ta-Wei

Abstract | Document (786 KB) | BibTeX

Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems

Authors: Day, Joel D. ; Kosche, Maria ; Manea, Florin ; Schmid, Markus L.

Abstract | Document (1,476 KB) | BibTeX

Succinct List Indexing in Optimal Time

Authors: Holland, William L.

Abstract | Document (798 KB) | BibTeX

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games

Authors: Ignatiev, Artur ; Mihajlin, Ivan ; Smal, Alexander

Abstract | Document (785 KB) | BibTeX

The Dispersive Art Gallery Problem

Authors: Rieck, Christian ; Scheffer, Christian

Abstract | Document (1,186 KB) | BibTeX

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

33rd International Symposium on Algorithms and Computation (ISAAC 2022)