Portal - ISAAC 2017

ISAAC 2017	December 9-12, 2017 - Phuket, Thailand
28th International Symposium on Algorithms and Computation (ISAAC 2017) Yoshio Okamoto and Takeshi Tokuyama (Eds.)
ISBN 978-3-95977-054-5, LIPICS Vol. 92	ISSN 1868-8969

Additional Information

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

Authors

de Montgolfier, Fabien

Freksen, Casper Benjamin

Kanté, Mamadou Moustapha

Kao, Mong-Jen

Katsikarelis, Ioannis

Konstantinidis, Athanasios L.

Levcopoulos, Christos

Mitchell, Joseph S. B.

Paschos, Vangelis Th.

Sidiropoulos, Anastasios

Stølting Brodal, Gerth

Thankachan, Sharma V.

Venkatasubramanian, Suresh

Front Matter, Table of Contents, Preface, External Reviewers

Authors: Okamoto, Yoshio ; Tokuyama, Takeshi

Abstract | Document (351 KB) | BibTeX

Weighted Linear Matroid Parity

Authors: Iwata, Satoru

Abstract | Document (365 KB) | BibTeX

Computational Philosophy: On Fairness in Automated Decision Making

Authors: Venkatasubramanian, Suresh

Abstract | Document (201 KB) | BibTeX

Faster Algorithms for Growing Prioritized Disks and Rectangles

Authors: Ahn, Hee-Kap ; Bae, Sang Won ; Choi, Jongmin ; Korman, Matias ; Mulzer, Wolfgang ; Oh, Eunjin ; Park, Ji-won ; van Renssen, André ; Vigneron, Antoine

Abstract | Document (662 KB) | BibTeX

Placing your Coins on a Shelf

Authors: Alt, Helmut ; Buchin, Kevin ; Chaplick, Steven ; Cheong, Otfried ; Kindermann, Philipp ; Knauer, Christian ; Stehn, Fabian

Abstract | Document (705 KB) | BibTeX

On the Number of p4-Tilings by an n-Omino

Authors: Amano, Kazuyuki ; Haruyama, Yoshinobu

Abstract | Document (1,875 KB) | BibTeX

Network Optimization on Partitioned Pairs of Points

Authors: Arkin, Esther M. ; Banik, Aritra ; Carmi, Paz ; Citovsky, Gui ; Jia, Su ; Katz, Matthew J. ; Mayer, Tyler ; Mitchell, Joseph S. B.

Abstract | Document (577 KB) | BibTeX

Voronoi Diagrams for Parallel Halflines and Line Segments in Space

Authors: Aurenhammer, Franz ; Jüttler, Bert ; Paulini, Günter

Abstract | Document (579 KB) | BibTeX

Faster Algorithms for Half-Integral T-Path Packing

Authors: Babenko, Maxim ; Artamonov, Stepan

Abstract | Document (576 KB) | BibTeX

Shortcuts for the Circle

Authors: Bae, Sang Won ; de Berg, Mark ; Cheong, Otfried ; Gudmundsson, Joachim ; Levcopoulos, Christos

Abstract | Document (797 KB) | BibTeX

Routing in Polygonal Domains

Authors: Banyassady, Bahareh ; Chiu, Man-Kwun ; Korman, Matias ; Mulzer, Wolfgang ; van Renssen, André ; Roeloffzen, Marcel ; Seiferth, Paul ; Stein, Yannik ; Vogtenhuber, Birgit ; Willert, Max

Abstract | Document (761 KB) | BibTeX

Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces

Authors: Becker, Aaron T. ; Fekete, Sándor P. ; Keldenich, Phillip ; Krupke, Dominik ; Rieck, Christian ; Scheffer, Christian ; Schmidt, Arne

Abstract | Document (2,691 KB) | BibTeX

A Simple Greedy Algorithm for Dynamic Graph Orientation

Authors: Berglin, Edvin ; Stølting Brodal, Gerth

Abstract | Document (463 KB) | BibTeX

Crossing Number for Graphs with Bounded~Pathwidth

Authors: Biedl, Therese ; Chimani, Markus ; Derka, Martin ; Mutzel, Petra

Abstract | Document (599 KB) | BibTeX

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

Authors: Bilò, Davide ; Colella, Feliciano ; Gualà, Luciano ; Leucci, Stefano ; Proietti, Guido

Abstract | Document (743 KB) | BibTeX

Decomposing a Graph into Shortest Paths with Bounded Eccentricity

Authors: Birmelé, Etienne ; de Montgolfier, Fabien ; Planche, Léo ; Viennot, Laurent

Abstract | Document (538 KB) | BibTeX

Independent Feedback Vertex Set for P_5-free Graphs

Authors: Bonamy, Marthe ; Dabrowski, Konrad K. ; Feghali, Carl ; Johnson, Matthew ; Paulusma, Daniël

Abstract | Document (582 KB) | BibTeX

On the Convergence Time of a Natural Dynamics for Linear Programming

Authors: Bonifaci, Vincenzo

Abstract | Document (420 KB) | BibTeX

Routing on the Visibility Graph

Authors: Bose, Prosenjit ; Korman, Matias ; van Renssen, André ; Verdonschot, Sander

Abstract | Document (618 KB) | BibTeX

An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint

Authors: Calinescu, Gruia ; Jaehn, Florian ; Li, Minming ; Wang, Kai

Abstract | Document (508 KB) | BibTeX

An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem

Authors: Chen, Li-Hsuan ; Hsieh, Sun-Yuan ; Hung, Ling-Ju ; Rossmanith, Peter

Abstract | Document (509 KB) | BibTeX

Smart Contract Execution - the (+-)-Biased Ballot Problem

Authors: Chen, Lin ; Xu, Lei ; Gao, Zhimin ; Shah, Nolan ; Lu, Yang ; Shi, Weidong

Abstract | Document (484 KB) | BibTeX

Study of a Combinatorial Game in Graphs Through Linear Programming

Authors: Cohen, Nathann ; Mc Inerney, Fionn ; Nisse, Nicolas ; Pérennes, Stéphane

Abstract | Document (753 KB) | BibTeX

On Maximal Cliques with Connectivity Constraints in Directed Graphs

Authors: Conte, Alessio ; Kanté, Mamadou Moustapha ; Uno, Takeaki ; Wasa, Kunihiro

Abstract | Document (557 KB) | BibTeX

Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs

Authors: Da Lozzo, Giordano ; Devanny, William E. ; Eppstein, David ; Johnson, Timothy

Abstract | Document (944 KB) | BibTeX

Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces

Authors: de Berg, Mark ; Gunawan, Ade ; Roeloffzen, Marcel

Abstract | Document (597 KB) | BibTeX

Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points

Authors: de Berg, Mark ; Leijsen, Tim ; Markovic, Aleksandar ; van Renssen, André ; Roeloffzen, Marcel ; Woeginger, Gerhard

Abstract | Document (578 KB) | BibTeX

Dynamic Conflict-Free Colorings in the Plane

Authors: de Berg, Mark ; Markovic, Aleksandar

Abstract | Document (489 KB) | BibTeX

Temporal Hierarchical Clustering

Authors: Dey, Tamal K. ; Rossi, Alfred ; Sidiropoulos, Anastasios

Abstract | Document (3,154 KB) | BibTeX

Agnostically Learning Boolean Functions with Finite Polynomial Representation

Authors: Ding, Ning

Abstract | Document (485 KB) | BibTeX

Succinct Color Searching in One Dimension

Authors: El-Zein, Hicham ; Munro, J. Ian ; Nekrich, Yakov

Abstract | Document (415 KB) | BibTeX

Conflict-Free Coloring of Intersection Graphs

Authors: Fekete, Sándor P. ; Keldenich, Phillip

Abstract | Document (726 KB) | BibTeX

On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms

Authors: Freksen, Casper Benjamin ; Larsen, Kasper Green

Abstract | Document (531 KB) | BibTeX

Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings

Authors: Fujishige, Yuta ; Nakashima, Yuto ; Inenaga, Shunsuke ; Bannai, Hideo ; Takeda, Masayuki

Abstract | Document (563 KB) | BibTeX

Embedding Graphs into Embedded Graphs

Authors: Fulek, Radoslav

Abstract | Document (575 KB) | BibTeX

Structural Pattern Matching - Succinctly

Authors: Ganguly, Arnab ; Shah, Rahul ; Thankachan, Sharma V.

Abstract | Document (639 KB) | BibTeX

On Structural Parameterizations of the Edge Disjoint Paths Problem

Authors: Ganian, Robert ; Ordyniak, Sebastian ; Sridharan, Ramanujan

Abstract | Document (512 KB) | BibTeX

Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements

Authors: Gaspers, Serge ; Gudmundsson, Joachim ; Mestre, Julián ; Rümmele, Stefan

Abstract | Document (690 KB) | BibTeX

Sorting with Recurrent Comparison Errors

Authors: Geissmann, Barbara ; Leucci, Stefano ; Liu, Chih-Hung ; Penna, Paolo

Abstract | Document (556 KB) | BibTeX

Dominance Product and High-Dimensional Closest Pair under L_infty

Authors: Gold, Omer ; Sharir, Micha

Abstract | Document (525 KB) | BibTeX

Orthogonal Vectors Indexing

Authors: Goldstein, Isaac ; Lewenstein, Moshe ; Porat, Ely

Abstract | Document (473 KB) | BibTeX

Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems

Authors: Golin, Mordecai J. ; Khodabande, Hadi ; Qin, Bo

Abstract | Document (612 KB) | BibTeX

Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons

Authors: Gudmundsson, Joachim ; Pagh, Rasmus

Abstract | Document (535 KB) | BibTeX

Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

Authors: Habib, Michel ; Mouatadid, Lalla

Abstract | Document (555 KB) | BibTeX

On-the-Fly Array Initialization in Less Space

Authors: Hagerup, Torben ; Kammer, Frank

Abstract | Document (518 KB) | BibTeX

On Directed Covering and Domination Problems

Authors: Hanaka, Tesshu ; Nishimura, Naomi ; Ono, Hirotaka

Abstract | Document (673 KB) | BibTeX

Settlement Fund Circulation Problem

Authors: Hayakawa, Hitoshi ; Ishii, Toshimasa ; Ono, Hirotaka ; Uno, Yushi

Abstract | Document (569 KB) | BibTeX

An Efficient Sum Query Algorithm for Distance-based Locally Dominating Functions

Authors: Huang, Ziyun ; Xu, Jinhui

Abstract | Document (909 KB) | BibTeX

Complexity of the Multi-Service Center Problem

Authors: Ito, Takehiro ; Kakimura, Naonori ; Kobayashi, Yusuke

Abstract | Document (506 KB) | BibTeX

Improved Algorithms for Scheduling Unsplittable Flows on Paths

Authors: Jahanjou, Hamidreza ; Kantor, Erez ; Rajaraman, Rajmohan

Abstract | Document (872 KB) | BibTeX

Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center

Authors: Katsikarelis, Ioannis ; Lampis, Michael ; Paschos, Vangelis Th.

Abstract | Document (547 KB) | BibTeX

Optimal Matroid Partitioning Problems

Authors: Kawase, Yasushi ; Kimura, Kei ; Makino, Kazuhisa ; Sumita, Hanna

Abstract | Document (587 KB) | BibTeX

Improved Bounds for Online Dominating Sets of Trees

Authors: Kobayashi, Koji M.

Abstract | Document (520 KB) | BibTeX

Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs

Authors: Konstantinidis, Athanasios L. ; Papadopoulos, Charis

Abstract | Document (529 KB) | BibTeX

Non-Crossing Geometric Steiner Arborescences

Authors: Kostitsyna, Irina ; Speckmann, Bettina ; Verbeek, Kevin

Abstract | Document (1,015 KB) | BibTeX

Precedence-Constrained Min Sum Set Cover

Authors: McClintock, Jessica ; Mestre, Julián ; Wirth, Anthony

Abstract | Document (524 KB) | BibTeX

Jointly Stable Matchings

Authors: Miyazaki, Shuichi ; Okamoto, Kazuya

Abstract | Document (489 KB) | BibTeX

Fast Compressed Self-Indexes with Deterministic Linear-Time Construction

Authors: Munro, J. Ian ; Navarro, Gonzalo ; Nekrich, Yakov

Abstract | Document (522 KB) | BibTeX

Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

Authors: Nagao, Atsuki ; Seto, Kazuhisa ; Teruyama, Junichi

Abstract | Document (467 KB) | BibTeX

Fully Dynamic Connectivity Oracles under General Vertex Updates

Authors: Nakamura, Kengo

Abstract | Document (509 KB) | BibTeX

Finding Pairwise Intersections of Rectangles in a Query Rectangle

Authors: Oh, Eunjin ; Ahn, Hee-Kap

Abstract | Document (526 KB) | BibTeX

A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms

Authors: Oh, Eunjin ; Ahn, Hee-Kap

Abstract | Document (628 KB) | BibTeX

Complexity of Coloring Reconfiguration under Recolorability Constraints

Authors: Osawa, Hiroki ; Suzuki, Akira ; Ito, Takehiro ; Zhou, Xiao

Abstract | Document (3,254 KB) | BibTeX

Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}

Authors: Sankowski, Piotr ; Wygocki, Piotr

Abstract | Document (583 KB) | BibTeX

Tight Approximation for Partial Vertex Cover with Hard Capacities

Authors: Shiau, Jia-Yau ; Kao, Mong-Jen ; Lin, Ching-Chi ; Lee, D. T.

Abstract | Document (515 KB) | BibTeX

Hybrid VCSPs with Crisp and Valued Conservative Templates

Authors: Takhanov, Rustem

Abstract | Document (474 KB) | BibTeX

A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

Authors: Xu, Yao ; Chen, Yong ; Lin, Guohui ; Liu, Tian ; Luo, Taibo ; Zhang, Peng

Abstract | Document (763 KB) | BibTeX

Envy-free Matchings with Lower Quotas

Authors: Yokoi, Yu

Abstract | Document (533 KB) | BibTeX

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

28th International Symposium on Algorithms and Computation (ISAAC 2017)