ISAAC 2018 December 16-19, 2018 - Jiaoxi, Yilan, Taiwan

29th International Symposium on Algorithms and Computation (ISAAC 2018)



Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao (Eds.)
ISBN 978-3-95977-094-1, LIPICS Vol. 123 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 33 MB)
Search Publication Server


Authors
  • Agarwal, Pankaj K.
  • Aggarwal, Divesh
  • Akutsu, Tatsuya
  • Angelini, Patrizio
  • Arimura, Hiroki
  • Arseneva, Elena
  • Aurenhammer, Franz
  • Avarikioti, Georgia
  • Bansal, Nikhil
  • Bekos, Michael A.
  • Ben Basat, Ran
  • Bentert, Matthias
  • Bezáková, Ivona
  • Bhattacharya, Binay
  • Bilň, Davide
  • Bishnu, Arijit
  • Björklund, Andreas
  • Blömer, Johannes
  • Bouchard, Sébastien
  • Bouts, Quirijn
  • Brauer, Sascha
  • Bujna, Kathrin
  • Castermans, Thom
  • Cevallos, Alfonso
  • Chakraborty, Samarjit
  • Chalermsook, Parinya
  • Chan, Timothy M.
  • Chen, Jian-Jia
  • Chen, Jiehua
  • Chen, Yen-Ting
  • Cheng, Siu-Wing
  • Chiu, Man-Kwun
  • Czygrinow, Andrzej
  • Da Lozzo, Giordano
  • Datta, Samir
  • Dieudonné, Yoann
  • Di Giacomo, Emilio
  • Dittmann, Alexander
  • Ducoffe, Guillaume
  • Dvorák, Pavel
  • Eades, Peter
  • Eisenbrand, Friedrich
  • Erlebach, Thomas
  • Farach-Colton, Martín
  • Feng, Qilong
  • Ficker, Annette M. C.
  • Fleszar, Krzysztof
  • Fotakis, Dimitris
  • Fu, Bin
  • Gagie, Travis
  • Garijo, Delia
  • Geary, Cody
  • Ghosh, Arijit
  • Gleich, David F.
  • Goswami, Mayank
  • Gourvčs, Laurent
  • H. Bshouty, Nader
  • Hanckowiak, Michal
  • Har-Peled, Sariel
  • He, Meng
  • Higashikawa, Yuya
  • Hirai, Hiroshi
  • Hoefer, Martin
  • Hong, Eunpyeong
  • Hoover, Kenneth
  • Hsu, Wen-Lian
  • Husfeldt, Thore
  • Impagliazzo, Russell
  • Ishizuka, Takashi
  • Ito, Takehiro
  • Iwamasa, Yuni
  • Jansson, Jesper
  • Jo, Seungbum
  • Johnson, Matthew P.
  • Kameda, Tsunehiko
  • Kamiyama, Naoyuki
  • Kammer, Frank
  • Kao, Mong-Jen
  • Kaplan, Haim
  • Kaski, Petteri
  • Katoh, Naoki
  • Kaufmann, Michael
  • Keikha, Vahideh
  • Kellerhals, Leon
  • Kim, Eun Jung
  • Kipper, Geva
  • Klein, Rolf
  • Klimosová, Tereza
  • Knop, Dusan
  • Kociumaka, Tomasz
  • Koivisto, Mikko
  • Kolay, Sudeshna
  • Korman, Matias
  • Kostitsyna, Irina
  • Kozma, László
  • Kulkarni, Raghav
  • Kumar, Ashish
  • Kundu, Ritu
  • Kunysz, Adam
  • Kurita, Kazuhiro
  • Löffler, Maarten
  • Lee, Der-Tsai
  • Li, Meng
  • Li, Ruiming
  • Liao, Chung-Shou
  • Liotta, Giuseppe
  • Liu, Xingwu
  • Lo, On-Hei S.
  • Luo, Kelin
  • Márquez, Alberto
  • Makhoul, Waseem
  • Malík, Josef
  • Markovic, Aleksandar
  • Masarík, Tomás
  • Matheny, Michael
  • Mathieu, Claire
  • Mehlhorn, Kurt
  • Meijer, Henk
  • Meulemans, Wouter
  • Meunier, Pierre-Étienne
  • Mihajlin, Ivan
  • Mihalák, Matús
  • Mishra, Gopinath
  • Mohamed, Manal
  • Molter, Hendrik
  • Montecchiani, Fabrizio
  • Morell, Sarah
  • Mukherjee, Anish
  • Mukhopadhyay, Priyanka
  • Mulzer, Wolfgang
  • Munro, J. Ian
  • N. Zehmakan, Ahad
  • Navarro, Gonzalo
  • Nichterlein, André
  • Niedermeier, Rolf
  • Novotná, Jana
  • Oh, Eunjin
  • Okamoto, Yoshio
  • Ooms, Aurélien
  • Osawa, Hiroki
  • Pan, Zhida
  • Papadopoulos, Kleitos
  • Paulusma, Daniël
  • Pelc, Andrzej
  • Petit, Franck
  • Pfister, Maximilian
  • Phillips, Jeff M.
  • Pilz, Alexander
  • Pissis, Solon P.
  • Popa, Alexandru
  • Preißer, Johanna E.
  • Rahman, Md Lutfar
  • Raz, Danny
  • Roditty, Liam
  • Rodríguez, Natalia
  • Roeloffzen, Marcel
  • Rote, Günter
  • Rutter, Ignaz
  • Sajenko, Andrej
  • Saranurak, Thatchaphol
  • Satti, Srinivasa Rao
  • Saurabh, Saket
  • Schabanel, Nicolas
  • Schmidt, Jens M.
  • Schnider, Patrick
  • Searns, Andrew
  • Seiferth, Paul
  • Seki, Shinnosuke
  • Serna, Maria
  • Shabtai, Galia
  • Sharir, Micha
  • Shavitt, Yuval
  • Silveira, Rodrigo I.
  • Slívová, Veronika
  • Smal, Alexander V.
  • Sorge, Manuel
  • Spieksma, Frits C. R.
  • Spoerhase, Joachim
  • Srivastav, Abhinav
  • Staals, Frank
  • Stein, Clifford
  • Steinkogler, Michael
  • Suchý, Ondrej
  • Suzuki, Akira
  • Takasu, Atsuhiro
  • Tamura, Takeyuki
  • Tan, Guanlan
  • Teng, Shang-Hua
  • Thilikos, Dimitrios M.
  • Toufar, Tomás
  • Tsai, Meng-Tsung
  • Tsai, Shi-Chun
  • Ueckerdt, Torsten
  • Ugare, Shubham
  • Uno, Takeaki
  • Urhausen, Jérôme
  • van de Kerkhof, Mees
  • van Dijk, Thomas C.
  • van Goethem, Arthur
  • van Kreveld, Marc
  • van Renssen, André
  • Veldt, Nate
  • Vermeulen, Jordi L.
  • von der Brüggen, Georg
  • Wang, Jianxin
  • Wang, Yuyi
  • Wasa, Kunihiro
  • Watson, Thomas
  • Wattenhofer, Roger
  • Wawrzyniak, Wojciech
  • Wilhelmi, Lisa
  • Willert, Max
  • Wiratma, Lionov
  • Wirth, Anthony
  • Witkowski, Marcin
  • Wolff, Alexander
  • Wu, Kaiyu
  • Xiao, Allen
  • Xu, Yinfeng
  • Yan, Lie
  • Zhou, Xiao
  • Zhu, Senmin

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Hsu, Wen-Lian ; Lee, Der-Tsai ; Liao, Chung-Shou

    Abstract | Document (326 KB) | BibTeX

    Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk)
    Authors: Teng, Shang-Hua

    Abstract | Document (159 KB) | BibTeX

    Approximate Matchings in Massive Graphs via Local Structure (Invited Talk)
    Authors: Stein, Clifford

    Abstract | Document (159 KB) | BibTeX

    Exploiting Sparsity for Bipartite Hamiltonicity
    Authors: Björklund, Andreas

    Abstract | Document (407 KB) | BibTeX

    Opinion Forming in Erdös-Rényi Random Graph and Expanders
    Authors: N. Zehmakan, Ahad

    Abstract | Document (452 KB) | BibTeX

    Colouring (P_r+P_s)-Free Graphs
    Authors: Klimosová, Tereza ; Malík, Josef ; Masarík, Tomás ; Novotná, Jana ; Paulusma, Daniël ; Slívová, Veronika

    Abstract | Document (473 KB) | BibTeX

    The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes
    Authors: Ducoffe, Guillaume ; Popa, Alexandru

    Abstract | Document (474 KB) | BibTeX

    A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
    Authors: Bilň, Davide ; Papadopoulos, Kleitos

    Abstract | Document (528 KB) | BibTeX

    Efficient Enumeration of Dominating Sets for Sparse Graphs
    Authors: Kurita, Kazuhiro ; Wasa, Kunihiro ; Arimura, Hiroki ; Uno, Takeaki

    Abstract | Document (511 KB) | BibTeX

    Complexity of Unordered CNF Games
    Authors: Rahman, Md Lutfar ; Watson, Thomas

    Abstract | Document (514 KB) | BibTeX

    Half-Duplex Communication Complexity
    Authors: Hoover, Kenneth ; Impagliazzo, Russell ; Mihajlin, Ivan ; Smal, Alexander V.

    Abstract | Document (436 KB) | BibTeX

    On the Complexity of Stable Fractional Hypergraph Matching
    Authors: Ishizuka, Takashi ; Kamiyama, Naoyuki

    Abstract | Document (655 KB) | BibTeX

    Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete
    Authors: Johnson, Matthew P.

    Abstract | Document (508 KB) | BibTeX

    Computing Vertex-Disjoint Paths in Large Graphs Using MAOs
    Authors: Preißer, Johanna E. ; Schmidt, Jens M.

    Abstract | Document (440 KB) | BibTeX

    An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks
    Authors: Bhattacharya, Binay ; Higashikawa, Yuya ; Kameda, Tsunehiko ; Katoh, Naoki

    Abstract | Document (560 KB) | BibTeX

    Computing Optimal Shortcuts for Networks
    Authors: Garijo, Delia ; Márquez, Alberto ; Rodríguez, Natalia ; Silveira, Rodrigo I.

    Abstract | Document (739 KB) | BibTeX

    Algorithmic Channel Design
    Authors: Avarikioti, Georgia ; Wang, Yuyi ; Wattenhofer, Roger

    Abstract | Document (409 KB) | BibTeX

    Counting Connected Subgraphs with Maximum-Degree-Aware Sieving
    Authors: Björklund, Andreas ; Husfeldt, Thore ; Kaski, Petteri ; Koivisto, Mikko

    Abstract | Document (383 KB) | BibTeX

    Target Set Selection in Dense Graph Classes
    Authors: Dvorák, Pavel ; Knop, Dusan ; Toufar, Tomás

    Abstract | Document (491 KB) | BibTeX

    Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm
    Authors: Björklund, Andreas ; Husfeldt, Thore

    Abstract | Document (436 KB) | BibTeX

    Data-Compression for Parametrized Counting Problems on Sparse Graphs
    Authors: Kim, Eun Jung ; Serna, Maria ; Thilikos, Dimitrios M.

    Abstract | Document (540 KB) | BibTeX

    Planar Maximum Matching: Towards a Parallel Algorithm
    Authors: Datta, Samir ; Kulkarni, Raghav ; Kumar, Ashish ; Mukherjee, Anish

    Abstract | Document (519 KB) | BibTeX

    Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
    Authors: Czygrinow, Andrzej ; Hanckowiak, Michal ; Wawrzyniak, Wojciech ; Witkowski, Marcin

    Abstract | Document (431 KB) | BibTeX

    Proving the Turing Universality of Oritatami Co-Transcriptional Folding
    Authors: Geary, Cody ; Meunier, Pierre-Étienne ; Schabanel, Nicolas ; Seki, Shinnosuke

    Abstract | Document (7,923 KB) | BibTeX

    Cluster Editing in Multi-Layer and Temporal Graphs
    Authors: Chen, Jiehua ; Molter, Hendrik ; Sorge, Manuel ; Suchý, Ondrej

    Abstract | Document (772 KB) | BibTeX

    Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers
    Authors: Bishnu, Arijit ; Ghosh, Arijit ; Kolay, Sudeshna ; Mishra, Gopinath ; Saurabh, Saket

    Abstract | Document (461 KB) | BibTeX

    Approximate Minimum-Weight Matching with Outliers Under Translation
    Authors: Agarwal, Pankaj K. ; Kaplan, Haim ; Kipper, Geva ; Mulzer, Wolfgang ; Rote, Günter ; Sharir, Micha ; Xiao, Allen

    Abstract | Document (535 KB) | BibTeX

    New and Improved Algorithms for Unordered Tree Inclusion
    Authors: Akutsu, Tatsuya ; Jansson, Jesper ; Li, Ruiming ; Takasu, Atsuhiro ; Tamura, Takeyuki

    Abstract | Document (531 KB) | BibTeX

    Beyond-Planarity: Turán-Type Results for Non-Planar Bipartite Graphs
    Authors: Angelini, Patrizio ; Bekos, Michael A. ; Kaufmann, Michael ; Pfister, Maximilian ; Ueckerdt, Torsten

    Abstract | Document (716 KB) | BibTeX

    A Dichotomy Result for Cyclic-Order Traversing Games
    Authors: Chen, Yen-Ting ; Tsai, Meng-Tsung ; Tsai, Shi-Chun

    Abstract | Document (483 KB) | BibTeX

    The b-Matching Problem in Distance-Hereditary Graphs and Beyond
    Authors: Ducoffe, Guillaume ; Popa, Alexandru

    Abstract | Document (534 KB) | BibTeX

    New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
    Authors: Feng, Qilong ; Tan, Guanlan ; Zhu, Senmin ; Fu, Bin ; Wang, Jianxin

    Abstract | Document (413 KB) | BibTeX

    Computing Approximate Statistical Discrepancy
    Authors: Matheny, Michael ; Phillips, Jeff M.

    Abstract | Document (884 KB) | BibTeX

    Diversity Maximization in Doubling Metrics
    Authors: Cevallos, Alfonso ; Eisenbrand, Friedrich ; Morell, Sarah

    Abstract | Document (477 KB) | BibTeX

    On Polynomial Time Constructions of Minimum Height Decision Tree
    Authors: H. Bshouty, Nader ; Makhoul, Waseem

    Abstract | Document (346 KB) | BibTeX

    Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm
    Authors: Aggarwal, Divesh ; Mukhopadhyay, Priyanka

    Abstract | Document (518 KB) | BibTeX

    An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
    Authors: Bentert, Matthias ; Dittmann, Alexander ; Kellerhals, Leon ; Nichterlein, André ; Niedermeier, Rolf

    Abstract | Document (570 KB) | BibTeX

    Algorithms for Coloring Reconfiguration Under Recolorability Constraints
    Authors: Osawa, Hiroki ; Suzuki, Akira ; Ito, Takehiro ; Zhou, Xiao

    Abstract | Document (1,011 KB) | BibTeX

    A Cut Tree Representation for Pendant Pairs
    Authors: Lo, On-Hei S. ; Schmidt, Jens M.

    Abstract | Document (425 KB) | BibTeX

    Polyline Drawings with Topological Constraints
    Authors: Di Giacomo, Emilio ; Eades, Peter ; Liotta, Giuseppe ; Meijer, Henk ; Montecchiani, Fabrizio

    Abstract | Document (582 KB) | BibTeX

    Almost Optimal Algorithms for Diameter-Optimally Augmenting Trees
    Authors: Bilň, Davide

    Abstract | Document (545 KB) | BibTeX

    Approximation Algorithms for Facial Cycles in Planar Embeddings
    Authors: Da Lozzo, Giordano ; Rutter, Ignaz

    Abstract | Document (656 KB) | BibTeX

    An Algorithm for the Maximum Weight Strongly Stable Matching Problem
    Authors: Kunysz, Adam

    Abstract | Document (441 KB) | BibTeX

    Approximation Algorithm for Vertex Cover with Multiple Covering Constraints
    Authors: Hong, Eunpyeong ; Kao, Mong-Jen

    Abstract | Document (364 KB) | BibTeX

    Correlation Clustering Generalized
    Authors: Gleich, David F. ; Veldt, Nate ; Wirth, Anthony

    Abstract | Document (474 KB) | BibTeX

    Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm
    Authors: Ficker, Annette M. C. ; Erlebach, Thomas ; Mihalák, Matús ; Spieksma, Frits C. R.

    Abstract | Document (439 KB) | BibTeX

    Coresets for Fuzzy K-Means with Applications
    Authors: Blömer, Johannes ; Brauer, Sascha ; Bujna, Kathrin

    Abstract | Document (423 KB) | BibTeX

    Streaming Algorithms for Planar Convex Hulls
    Authors: Farach-Colton, Martín ; Li, Meng ; Tsai, Meng-Tsung

    Abstract | Document (512 KB) | BibTeX

    Deterministic Treasure Hunt in the Plane with Angular Hints
    Authors: Bouchard, Sébastien ; Dieudonné, Yoann ; Pelc, Andrzej ; Petit, Franck

    Abstract | Document (529 KB) | BibTeX

    Competitive Searching for a Line on a Line Arrangement
    Authors: Bouts, Quirijn ; Castermans, Thom ; van Goethem, Arthur ; van Kreveld, Marc ; Meulemans, Wouter

    Abstract | Document (689 KB) | BibTeX

    Stabbing Pairwise Intersecting Disks by Five Points
    Authors: Har-Peled, Sariel ; Kaplan, Haim ; Mulzer, Wolfgang ; Roditty, Liam ; Seiferth, Paul ; Sharir, Micha ; Willert, Max

    Abstract | Document (747 KB) | BibTeX

    Point Location in Incremental Planar Subdivisions
    Authors: Oh, Eunjin

    Abstract | Document (534 KB) | BibTeX

    Convex Partial Transversals of Planar Regions
    Authors: Keikha, Vahideh ; van de Kerkhof, Mees ; van Kreveld, Marc ; Kostitsyna, Irina ; Löffler, Maarten ; Staals, Frank ; Urhausen, Jérôme ; Vermeulen, Jordi L. ; Wiratma, Lionov

    Abstract | Document (662 KB) | BibTeX

    Extending the Centerpoint Theorem to Multiple Points
    Authors: Pilz, Alexander ; Schnider, Patrick

    Abstract | Document (524 KB) | BibTeX

    Approximate Query Processing over Static Sets and Sliding Windows
    Authors: Ben Basat, Ran ; Jo, Seungbum ; Satti, Srinivasa Rao ; Ugare, Shubham

    Abstract | Document (587 KB) | BibTeX

    Multi-Finger Binary Search Trees
    Authors: Chalermsook, Parinya ; Goswami, Mayank ; Kozma, László ; Mehlhorn, Kurt ; Saranurak, Thatchaphol

    Abstract | Document (626 KB) | BibTeX

    On Counting Oracles for Path Problems
    Authors: Bezáková, Ivona ; Searns, Andrew

    Abstract | Document (452 KB) | BibTeX

    Reconstructing Phylogenetic Tree From Multipartite Quartet System
    Authors: Hirai, Hiroshi ; Iwamasa, Yuni

    Abstract | Document (1,895 KB) | BibTeX

    Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
    Authors: Arseneva, Elena ; Chiu, Man-Kwun ; Korman, Matias ; Markovic, Aleksandar ; Okamoto, Yoshio ; Ooms, Aurélien ; van Renssen, André ; Roeloffzen, Marcel

    Abstract | Document (433 KB) | BibTeX

    Minimizing Distance-to-Sight in Polygonal Domains
    Authors: Oh, Eunjin

    Abstract | Document (510 KB) | BibTeX

    Partially Walking a Polygon
    Authors: Aurenhammer, Franz ; Steinkogler, Michael ; Klein, Rolf

    Abstract | Document (333 KB) | BibTeX

    Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity
    Authors: Chan, Timothy M. ; van Dijk, Thomas C. ; Fleszar, Krzysztof ; Spoerhase, Joachim ; Wolff, Alexander

    Abstract | Document (628 KB) | BibTeX

    Impatient Online Matching
    Authors: Liu, Xingwu ; Pan, Zhida ; Wang, Yuyi ; Wattenhofer, Roger

    Abstract | Document (592 KB) | BibTeX

    Extensions of Self-Improving Sorters
    Authors: Cheng, Siu-Wing ; Yan, Lie

    Abstract | Document (423 KB) | BibTeX

    Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings
    Authors: Luo, Kelin ; Erlebach, Thomas ; Xu, Yinfeng

    Abstract | Document (473 KB) | BibTeX

    Packing Returning Secretaries
    Authors: Hoefer, Martin ; Wilhelmi, Lisa

    Abstract | Document (463 KB) | BibTeX

    Simple 2^f-Color Choice Dictionaries
    Authors: Kammer, Frank ; Sajenko, Andrej

    Abstract | Document (477 KB) | BibTeX

    Succinct Data Structures for Chordal Graphs
    Authors: Munro, J. Ian ; Wu, Kaiyu

    Abstract | Document (383 KB) | BibTeX

    Tree Path Majority Data Structures
    Authors: Gagie, Travis ; He, Meng ; Navarro, Gonzalo

    Abstract | Document (441 KB) | BibTeX

    Encoding Two-Dimensional Range Top-k Queries Revisited
    Authors: Jo, Seungbum ; Satti, Srinivasa Rao

    Abstract | Document (495 KB) | BibTeX

    Longest Unbordered Factor in Quasilinear Time
    Authors: Kociumaka, Tomasz ; Kundu, Ritu ; Mohamed, Manal ; Pissis, Solon P.

    Abstract | Document (584 KB) | BibTeX

    Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems
    Authors: Chen, Jian-Jia ; Bansal, Nikhil ; Chakraborty, Samarjit ; von der Brüggen, Georg

    Abstract | Document (502 KB) | BibTeX

    A Relaxed FPTAS for Chance-Constrained Knapsack
    Authors: Shabtai, Galia ; Raz, Danny ; Shavitt, Yuval

    Abstract | Document (530 KB) | BibTeX

    Covering Clients with Types and Budgets
    Authors: Fotakis, Dimitris ; Gourvčs, Laurent ; Mathieu, Claire ; Srivastav, Abhinav

    Abstract | Document (445 KB) | BibTeX

      




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