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
  • Ahn, Hee-Kap
  • Alt, Helmut
  • Amano, Kazuyuki
  • Arkin, Esther M.
  • Artamonov, Stepan
  • Aurenhammer, Franz
  • Babenko, Maxim
  • Bae, Sang Won
  • Banik, Aritra
  • Bannai, Hideo
  • Banyassady, Bahareh
  • Becker, Aaron T.
  • Berglin, Edvin
  • Biedl, Therese
  • Bilň, Davide
  • Birmelé, Etienne
  • Bonamy, Marthe
  • Bonifaci, Vincenzo
  • Bose, Prosenjit
  • Buchin, Kevin
  • Calinescu, Gruia
  • Carmi, Paz
  • Chaplick, Steven
  • Chen, Li-Hsuan
  • Chen, Lin
  • Chen, Yong
  • Cheong, Otfried
  • Chimani, Markus
  • Chiu, Man-Kwun
  • Choi, Jongmin
  • Citovsky, Gui
  • Cohen, Nathann
  • Colella, Feliciano
  • Conte, Alessio
  • Dabrowski, Konrad K.
  • Da Lozzo, Giordano
  • de Berg, Mark
  • de Montgolfier, Fabien
  • Derka, Martin
  • Devanny, William E.
  • Dey, Tamal K.
  • Ding, Ning
  • El-Zein, Hicham
  • Eppstein, David
  • Feghali, Carl
  • Fekete, Sándor P.
  • Freksen, Casper Benjamin
  • Fujishige, Yuta
  • Fulek, Radoslav
  • Ganguly, Arnab
  • Ganian, Robert
  • Gao, Zhimin
  • Gaspers, Serge
  • Geissmann, Barbara
  • Gold, Omer
  • Goldstein, Isaac
  • Golin, Mordecai J.
  • Gualŕ, Luciano
  • Gudmundsson, Joachim
  • Gunawan, Ade
  • Habib, Michel
  • Hagerup, Torben
  • Hanaka, Tesshu
  • Haruyama, Yoshinobu
  • Hayakawa, Hitoshi
  • Hsieh, Sun-Yuan
  • Huang, Ziyun
  • Hung, Ling-Ju
  • Inenaga, Shunsuke
  • Ishii, Toshimasa
  • Ito, Takehiro
  • Iwata, Satoru
  • Jüttler, Bert
  • Jaehn, Florian
  • Jahanjou, Hamidreza
  • Jia, Su
  • Johnson, Matthew
  • Johnson, Timothy
  • Kakimura, Naonori
  • Kammer, Frank
  • Kanté, Mamadou Moustapha
  • Kantor, Erez
  • Kao, Mong-Jen
  • Katsikarelis, Ioannis
  • Katz, Matthew J.
  • Kawase, Yasushi
  • Keldenich, Phillip
  • Khodabande, Hadi
  • Kimura, Kei
  • Kindermann, Philipp
  • Knauer, Christian
  • Kobayashi, Koji M.
  • Kobayashi, Yusuke
  • Konstantinidis, Athanasios L.
  • Korman, Matias
  • Kostitsyna, Irina
  • Krupke, Dominik
  • Lampis, Michael
  • Larsen, Kasper Green
  • Lee, D. T.
  • Leijsen, Tim
  • Leucci, Stefano
  • Levcopoulos, Christos
  • Lewenstein, Moshe
  • Li, Minming
  • Lin, Ching-Chi
  • Lin, Guohui
  • Liu, Chih-Hung
  • Liu, Tian
  • Lu, Yang
  • Luo, Taibo
  • Makino, Kazuhisa
  • Markovic, Aleksandar
  • Mayer, Tyler
  • McClintock, Jessica
  • Mc Inerney, Fionn
  • Mestre, Julián
  • Mitchell, Joseph S. B.
  • Miyazaki, Shuichi
  • Mouatadid, Lalla
  • Mulzer, Wolfgang
  • Munro, J. Ian
  • Mutzel, Petra
  • Nagao, Atsuki
  • Nakamura, Kengo
  • Nakashima, Yuto
  • Navarro, Gonzalo
  • Nekrich, Yakov
  • Nishimura, Naomi
  • Nisse, Nicolas
  • Oh, Eunjin
  • Okamoto, Kazuya
  • Okamoto, Yoshio
  • Ono, Hirotaka
  • Ordyniak, Sebastian
  • Osawa, Hiroki
  • Pérennes, Stéphane
  • Pagh, Rasmus
  • Papadopoulos, Charis
  • Park, Ji-won
  • Paschos, Vangelis Th.
  • Paulini, Günter
  • Paulusma, Daniël
  • Penna, Paolo
  • Planche, Léo
  • Porat, Ely
  • Proietti, Guido
  • Qin, Bo
  • Rümmele, Stefan
  • Rajaraman, Rajmohan
  • Rieck, Christian
  • Roeloffzen, Marcel
  • Rossi, Alfred
  • Rossmanith, Peter
  • Sankowski, Piotr
  • Scheffer, Christian
  • Schmidt, Arne
  • Seiferth, Paul
  • Seto, Kazuhisa
  • Shah, Nolan
  • Shah, Rahul
  • Sharir, Micha
  • Shi, Weidong
  • Shiau, Jia-Yau
  • Sidiropoulos, Anastasios
  • Speckmann, Bettina
  • Sridharan, Ramanujan
  • Střlting Brodal, Gerth
  • Stehn, Fabian
  • Stein, Yannik
  • Sumita, Hanna
  • Suzuki, Akira
  • Takeda, Masayuki
  • Takhanov, Rustem
  • Teruyama, Junichi
  • Thankachan, Sharma V.
  • Tokuyama, Takeshi
  • Uno, Takeaki
  • Uno, Yushi
  • van Renssen, André
  • Venkatasubramanian, Suresh
  • Verbeek, Kevin
  • Verdonschot, Sander
  • Viennot, Laurent
  • Vigneron, Antoine
  • Vogtenhuber, Birgit
  • Wang, Kai
  • Wasa, Kunihiro
  • Willert, Max
  • Wirth, Anthony
  • Woeginger, Gerhard
  • Wygocki, Piotr
  • Xu, Jinhui
  • Xu, Lei
  • Xu, Yao
  • Yokoi, Yu
  • Zhang, Peng
  • Zhou, Xiao

  •   
    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 Published by LZI