Portal - ISAAC 2018

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

Chakraborty, Samarjit

Eisenbrand, Friedrich

Erlebach, Thomas

Farach-Colton, Martín

Feng, Qilong

Ficker, Annette M. C.

Meunier, Pierre-Étienne

Montecchiani, Fabrizio

Morell, Sarah

Mukherjee, Anish

Mukhopadhyay, Priyanka

Papadopoulos, Kleitos

Saranurak, Thatchaphol

Spieksma, Frits C. R.

Thilikos, Dimitrios M.

von der Brüggen, Georg

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

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