ISAAC 2019 December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China

30th International Symposium on Algorithms and Computation (ISAAC 2019)



Pinyan Lu and Guochuan Zhang (Eds.)
ISBN 978-3-95977-130-6, LIPICS Vol. 149 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 39 MB)
Search Publication Server

Authors
  • Agrawal, Akanksha
  • Akitaya, Hugo A.
  • Albers, Susanne
  • Alves Akitaya, Hugo
  • Arvind, V.
  • Ashvinkumar, Vikrant
  • Bae, Sang Won
  • Bannai, Hideo
  • Barequet, Gill
  • Bar-Noy, Amotz
  • Becchetti, Luca
  • Bhattacharya, Anup
  • Bhattacharya, Binay
  • Bienkowski, Marcin
  • Bille, Philip
  • Bishnu, Arijit
  • Böhnlein, Toni
  • Bonnet, Édouard
  • Bousquet, Nicolas
  • Bredereck, Robert
  • Brokkelkamp, Ruben
  • Bshouty, Nader H.
  • Buchin, Maike
  • Cao, Yixin
  • Charalampopoulos, Panagiotis
  • Chatterjee, Abhranil
  • Chen, Wei
  • Chen, Yong
  • Choudhary, Keerti
  • Cormode, Graham
  • Crespelle, Christophe
  • Cruciani, Emilio
  • Dasler, Philip
  • Das, Sandip
  • Datta, Rajit
  • de Berg, Mark
  • Defrain, Oscar
  • De Stefani, Lorenzo
  • Dev, Subhadeep Ranjan
  • Efrat, Alon
  • El-Zein, Hicham
  • Epa, Narthana S.
  • Eppstein, David
  • Fagerberg, Rolf
  • Feghali, Carl
  • Feng, Qilong
  • Flocchini, Paola
  • Fox, Kyle
  • Frei, Fabian
  • Frishberg, Daniel
  • Fujishige, Yuta
  • Galby, Esther
  • Ganardi, Moses
  • Gan, Junhao
  • Gaspers, Serge
  • Gawrychowski, Pawel
  • Geissmann, Barbara
  • Ghodselahi, Abdolhamid
  • Ghosh, Arijit
  • Goebel, Randy
  • Goldstein, Isaac
  • Golovach, Petr A.
  • Goodrich, Michael T.
  • Gørtz, Inge Li
  • Gudmundsson, Joachim
  • Hamada, Koki
  • Hammer, David
  • Han, Xin
  • Haraguchi, Kazuya
  • Heeger, Klaus
  • He, Meng
  • Hickey, Chris
  • Hoi, Gordon
  • Huang, Ziyun
  • Hucke, Danny
  • Iacono, John
  • Inenaga, Shunsuke
  • Inkulu, R.
  • Jain, Rahul
  • Jez, Lukasz
  • Kahle, Matthew
  • Kapoor, Sanjiv
  • Karsin, Ben
  • Kawase, Yasushi
  • Kazi, Serikzhan
  • Kilgus, Bernhard
  • Killick, Ryan
  • Kisfaludi-Bak, Sándor
  • Knop, Dusan
  • Kobayashi, Yasuaki
  • Kobourov, Stephen
  • Kociumaka, Tomasz
  • Kolay, Sudeshna
  • Koumoutsos, Grigorios
  • Kranakis, Evangelos
  • Kuhn, Fabian
  • Kulikov, Alexander S.
  • Ladewig, Leon
  • Landau, Gad M.
  • Lau, Joshua
  • Leucci, Stefano
  • Levcopoulos, Christos
  • Lewenstein, Moshe
  • Lima, Paloma T.
  • Liu, Chih-Hung
  • Liu, James A.
  • Li, Xinyi
  • Lohrey, Markus
  • Lotker, Zvi
  • Lu, Pinyan
  • Madathil, Jayakrishnan
  • Makino, Kazuhisa
  • Mamano, Nil
  • Marx, Dániel
  • Matias, Pedro
  • Mazzetto, Alessio
  • Mehr, Mehran
  • Meyer, Ulrich
  • Mikhailin, Ivan
  • Mishra, Gopinath
  • Miyazaki, Shuichi
  • Mohamed, Manal
  • Mokhov, Andrey
  • Mount, David M.
  • Mukhopadhyay, Partha
  • Munro, J. Ian
  • Nagamochi, Hiroshi
  • Nakashima, Yuto
  • Naori, David
  • Nekrich, Yakov
  • Nguyen Kim, Thang
  • Niedermeier, Rolf
  • Nilsson, Bengt J.
  • Nourine, Lhouari
  • Papadopoulou, Evanthia
  • Papp, Pál András
  • Pasquale, Francesco
  • Peleg, David
  • Peng, Binghui
  • Penna, Paolo
  • Pietracaprina, Andrea
  • Podolskii, Vladimir
  • Polak, Sven
  • Polishchuk, Valentin
  • Porat, Ely
  • Proietti, Guido
  • Pucci, Geppino
  • Radoszewski, Jakub
  • Rawitz, Dror
  • Raz, Danny
  • Ries, Bernard
  • Rizzo, Sara
  • Rong, Guozhen
  • Rytter, Wojciech
  • Ryvkin, Leonie
  • Sandlund, Bryce
  • Santoro, Nicola
  • Saurabh, Saket
  • Schäfer, Guido
  • Scheder, Dominik
  • Schmidt, Pawel
  • Sijben, Stef
  • Starikovskaya, Tatiana
  • Stephan, Frank
  • Su, Bing
  • Suderland, Martin
  • Suetsugu, Koki
  • Takeda, Masayuki
  • Tang, Shuyang
  • Tewari, Raghunath
  • Thomassé, Stéphan
  • Tian, Minghao
  • Tong, Weitian
  • Tsuiki, Hideki
  • Turau, Volker
  • Uehara, Ryuhei
  • Urhausen, Jérôme
  • van der Zanden, Tom C.
  • van Renssen, André
  • Velaj, Yllka
  • Wada, Koichi
  • Walen, Tomasz
  • Wang, Jianxin
  • Wang, Yusu
  • Wang, Zhifeng
  • Watrigant, Rémi
  • Wattenhofer, Roger
  • Weimann, Oren
  • Wenk, Carola
  • Wirth, Anthony
  • Xu, Jinhui
  • Xu, Yao
  • Yamashita, Masafumi
  • Yanagisawa, Hiroki
  • Yokomaku, Haruki
  • Zehmakan, Ahad N.
  • Zhang, An
  • Zhang, Guochuan
  • Zhang, Jiaheng
  • Zhang, Zhen
    		•

    		  
    Front Matter, Table of Contents, Preface, Symposium Organization
    Authors: Lu, Pinyan ; Zhang, Guochuan

    Abstract | Document (332 KB) | BibTeX

    Graph Searches and Their End Vertices
    Authors: Cao, Yixin ; Wang, Zhifeng ; Rong, Guozhen ; Wang, Jianxin

    Abstract | Document (589 KB) | BibTeX

    Lower Bound for Non-Adaptive Estimation of the Number of Defective Items
    Authors: Bshouty, Nader H.

    Abstract | Document (438 KB) | BibTeX

    A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions
    Authors: Haraguchi, Kazuya ; Nagamochi, Hiroshi

    Abstract | Document (602 KB) | BibTeX

    Top Tree Compression of Tries
    Authors: Bille, Philip ; Gawrychowski, Pawel ; Gørtz, Inge Li ; Landau, Gad M. ; Weimann, Oren

    Abstract | Document (4,624 KB) | BibTeX

    Two Phase Transitions in Two-Way Bootstrap Percolation
    Authors: Zehmakan, Ahad N.

    Abstract | Document (695 KB) | BibTeX

    Sliding Window Property Testing for Regular Languages
    Authors: Ganardi, Moses ; Hucke, Danny ; Lohrey, Markus ; Starikovskaya, Tatiana

    Abstract | Document (462 KB) | BibTeX

    On the Hardness of Set Disjointness and Set Intersection with Bounded Universe
    Authors: Goldstein, Isaac ; Lewenstein, Moshe ; Porat, Ely

    Abstract | Document (552 KB) | BibTeX

    Gathering and Election by Mobile Robots in a Continuous Cycle
    Authors: Flocchini, Paola ; Killick, Ryan ; Kranakis, Evangelos ; Santoro, Nicola ; Yamashita, Masafumi

    Abstract | Document (574 KB) | BibTeX

    Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists
    Authors: Hamada, Koki ; Miyazaki, Shuichi ; Yanagisawa, Hiroki

    Abstract | Document (485 KB) | BibTeX

    Online Multidimensional Packing Problems in the Random-Order Model
    Authors: Naori, David ; Raz, Danny

    Abstract | Document (493 KB) | BibTeX

    Approximate Euclidean Shortest Paths in Polygonal Domains
    Authors: Inkulu, R. ; Kapoor, Sanjiv

    Abstract | Document (647 KB) | BibTeX

    Reachability in High Treewidth Graphs
    Authors: Jain, Rahul ; Tewari, Raghunath

    Abstract | Document (560 KB) | BibTeX

    Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node
    Authors: Brokkelkamp, Ruben ; Polak, Sven ; Schäfer, Guido ; Velaj, Yllka

    Abstract | Document (723 KB) | BibTeX

    Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics
    Authors: Bienkowski, Marcin ; Jez, Lukasz ; Schmidt, Pawel

    Abstract | Document (494 KB) | BibTeX

    Measure and Conquer for Max Hamming Distance XSAT
    Authors: Hoi, Gordon ; Stephan, Frank

    Abstract | Document (472 KB) | BibTeX

    Cyclability in Graph Classes
    Authors: Crespelle, Christophe ; Feghali, Carl ; Golovach, Petr A.

    Abstract | Document (573 KB) | BibTeX

    Complexity of Linear Operators
    Authors: Kulikov, Alexander S. ; Mikhailin, Ivan ; Mokhov, Andrey ; Podolskii, Vladimir

    Abstract | Document (468 KB) | BibTeX

    New Results for the k-Secretary Problem
    Authors: Albers, Susanne ; Ladewig, Leon

    Abstract | Document (601 KB) | BibTeX

    Triangle Estimation Using Tripartite Independent Set Queries
    Authors: Bhattacharya, Anup ; Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath

    Abstract | Document (668 KB) | BibTeX

    Step-By-Step Community Detection in Volume-Regular Graphs
    Authors: Becchetti, Luca ; Cruciani, Emilio ; Pasquale, Francesco ; Rizzo, Sara

    Abstract | Document (657 KB) | BibTeX

    Blocking Dominating Sets for H-Free Graphs via Edge Contractions
    Authors: Galby, Esther ; Lima, Paloma T. ; Ries, Bernard

    Abstract | Document (516 KB) | BibTeX

    Internal Dictionary Matching
    Authors: Charalampopoulos, Panagiotis ; Kociumaka, Tomasz ; Mohamed, Manal ; Radoszewski, Jakub ; Rytter, Wojciech ; Walen, Tomasz

    Abstract | Document (601 KB) | BibTeX

    Approximating the Geometric Edit Distance
    Authors: Fox, Kyle ; Li, Xinyi

    Abstract | Document (608 KB) | BibTeX

    On Adaptivity Gaps of Influence Maximization Under the Independent Cascade Model with Full-Adoption Feedback
    Authors: Chen, Wei ; Peng, Binghui

    Abstract | Document (503 KB) | BibTeX

    Minimum-Width Double-Strip and Parallelogram Annulus
    Authors: Bae, Sang Won

    Abstract | Document (582 KB) | BibTeX

    Small Candidate Set for Translational Pattern Search
    Authors: Huang, Ziyun ; Feng, Qilong ; Wang, Jianxin ; Xu, Jinhui

    Abstract | Document (478 KB) | BibTeX

    The Weighted k-Center Problem in Trees for Fixed k
    Authors: Bhattacharya, Binay ; Das, Sandip ; Dev, Subhadeep Ranjan

    Abstract | Document (612 KB) | BibTeX

    Online Knapsack Problems with a Resource Buffer
    Authors: Han, Xin ; Kawase, Yasushi ; Makino, Kazuhisa ; Yokomaku, Haruki

    Abstract | Document (556 KB) | BibTeX

    Local Cliques in ER-Perturbed Random Geometric Graphs
    Authors: Kahle, Matthew ; Tian, Minghao ; Wang, Yusu

    Abstract | Document (711 KB) | BibTeX

    Local Routing in Sparse and Lightweight Geometric Graphs
    Authors: Ashvinkumar, Vikrant ; Gudmundsson, Joachim ; Levcopoulos, Christos ; Nilsson, Bengt J. ; van Renssen, André

    Abstract | Document (600 KB) | BibTeX

    Searching for Cryptogenography Upper Bounds via Sum of Square Programming
    Authors: Scheder, Dominik ; Tang, Shuyang ; Zhang, Jiaheng

    Abstract | Document (563 KB) | BibTeX

    On the Complexity of Lattice Puzzles
    Authors: Kobayashi, Yasuaki ; Suetsugu, Koki ; Tsuiki, Hideki ; Uehara, Ryuhei

    Abstract | Document (1,490 KB) | BibTeX

    The I/O Complexity of Hybrid Algorithms for Square Matrix Multiplication
    Authors: De Stefani, Lorenzo

    Abstract | Document (647 KB) | BibTeX

    Accurate MapReduce Algorithms for k-Median and k-Means in General Metric Spaces
    Authors: Mazzetto, Alessio ; Pietracaprina, Andrea ; Pucci, Geppino

    Abstract | Document (544 KB) | BibTeX

    On Optimal Balance in B-Trees: What Does It Cost to Stay in Perfect Shape?
    Authors: Fagerberg, Rolf ; Hammer, David ; Meyer, Ulrich

    Abstract | Document (500 KB) | BibTeX

    How Does Object Fatness Impact the Complexity of Packing in d Dimensions?
    Authors: Kisfaludi-Bak, Sándor ; Marx, Dániel ; van der Zanden, Tom C.

    Abstract | Document (3,743 KB) | BibTeX

    On One-Round Discrete Voronoi Games
    Authors: de Berg, Mark ; Kisfaludi-Bak, Sándor ; Mehr, Mehran

    Abstract | Document (709 KB) | BibTeX

    On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
    Authors: Arvind, V. ; Chatterjee, Abhranil ; Datta, Rajit ; Mukhopadhyay, Partha

    Abstract | Document (487 KB) | BibTeX

    A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing
    Authors: Nguyen Kim, Thang

    Abstract | Document (467 KB) | BibTeX

    An Improved Data Structure for Left-Right Maximal Generic Words Problem
    Authors: Fujishige, Yuta ; Nakashima, Yuto ; Inenaga, Shunsuke ; Bannai, Hideo ; Takeda, Masayuki

    Abstract | Document (715 KB) | BibTeX

    Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices
    Authors: Agrawal, Akanksha ; Kolay, Sudeshna ; Madathil, Jayakrishnan ; Saurabh, Saket

    Abstract | Document (2,869 KB) | BibTeX

    The Generalized Microscopic Image Reconstruction Problem
    Authors: Bar-Noy, Amotz ; Böhnlein, Toni ; Lotker, Zvi ; Peleg, David ; Rawitz, Dror

    Abstract | Document (489 KB) | BibTeX

    Stabilization Time in Minority Processes
    Authors: Papp, Pál András ; Wattenhofer, Roger

    Abstract | Document (549 KB) | BibTeX

    Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
    Authors: Bredereck, Robert ; Heeger, Klaus ; Knop, Dusan ; Niedermeier, Rolf

    Abstract | Document (592 KB) | BibTeX

    Path and Ancestor Queries over Trees with Multidimensional Weight Vectors
    Authors: He, Meng ; Kazi, Serikzhan

    Abstract | Document (582 KB) | BibTeX

    A 21/16-Approximation for the Minimum 3-Path Partition Problem
    Authors: Chen, Yong ; Goebel, Randy ; Su, Bing ; Tong, Weitian ; Xu, Yao ; Zhang, An

    Abstract | Document (580 KB) | BibTeX

    Efficiently Realizing Interval Sequences
    Authors: Bar-Noy, Amotz ; Choudhary, Keerti ; Peleg, David ; Rawitz, Dror

    Abstract | Document (581 KB) | BibTeX

    Efficient Interactive Proofs for Linear Algebra
    Authors: Cormode, Graham ; Hickey, Chris

    Abstract | Document (636 KB) | BibTeX

    When Maximum Stable Set Can Be Solved in FPT Time
    Authors: Bonnet, Édouard ; Bousquet, Nicolas ; Thomassé, Stéphan ; Watrigant, Rémi

    Abstract | Document (614 KB) | BibTeX

    The k-Fréchet Distance: How to Walk Your Dog While Teleporting
    Authors: Alves Akitaya, Hugo ; Buchin, Maike ; Ryvkin, Leonie ; Urhausen, Jérôme

    Abstract | Document (754 KB) | BibTeX

    New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs
    Authors: Mamano, Nil ; Efrat, Alon ; Eppstein, David ; Frishberg, Daniel ; Goodrich, Michael T. ; Kobourov, Stephen ; Matias, Pedro ; Polishchuk, Valentin

    Abstract | Document (683 KB) | BibTeX

    Efficient Circuit Simulation in MapReduce
    Authors: Frei, Fabian ; Wada, Koichi

    Abstract | Document (578 KB) | BibTeX

    Concurrent Distributed Serving with Mobile Servers
    Authors: Ghodselahi, Abdolhamid ; Kuhn, Fabian ; Turau, Volker

    Abstract | Document (807 KB) | BibTeX

    Tracking Paths in Planar Graphs
    Authors: Eppstein, David ; Goodrich, Michael T. ; Liu, James A. ; Matias, Pedro

    Abstract | Document (693 KB) | BibTeX

    Distance Measures for Embedded Graphs
    Authors: Akitaya, Hugo A. ; Buchin, Maike ; Kilgus, Bernhard ; Sijben, Stef ; Wenk, Carola

    Abstract | Document (1,305 KB) | BibTeX

    Online Algorithms for Warehouse Management
    Authors: Dasler, Philip ; Mount, David M.

    Abstract | Document (907 KB) | BibTeX

    On Approximate Range Mode and Range Selection
    Authors: El-Zein, Hicham ; He, Meng ; Munro, J. Ian ; Nekrich, Yakov ; Sandlund, Bryce

    Abstract | Document (596 KB) | BibTeX

    External Memory Planar Point Location with Fast Updates
    Authors: Iacono, John ; Karsin, Ben ; Koumoutsos, Grigorios

    Abstract | Document (716 KB) | BibTeX

    Minimizing and Computing the Inverse Geodesic Length on Trees
    Authors: Gaspers, Serge ; Lau, Joshua

    Abstract | Document (582 KB) | BibTeX

    Result-Sensitive Binary Search with Noisy Information
    Authors: Epa, Narthana S. ; Gan, Junhao ; Wirth, Anthony

    Abstract | Document (801 KB) | BibTeX

    Improved Algorithms for Clustering with Outliers
    Authors: Feng, Qilong ; Zhang, Zhen ; Huang, Ziyun ; Xu, Jinhui ; Wang, Jianxin

    Abstract | Document (552 KB) | BibTeX

    Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions
    Authors: Barequet, Gill ; Papadopoulou, Evanthia ; Suderland, Martin

    Abstract | Document (1,390 KB) | BibTeX

    Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P_7 - Free and P_8 - Free Chordal Graphs
    Authors: Defrain, Oscar ; Nourine, Lhouari

    Abstract | Document (720 KB) | BibTeX

    Dual-Mode Greedy Algorithms Can Save Energy
    Authors: Geissmann, Barbara ; Leucci, Stefano ; Liu, Chih-Hung ; Penna, Paolo ; Proietti, Guido

    Abstract | Document (785 KB) | BibTeX

    		  



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