ISAAC 2016 December 12-14, 2016 - Sydney, Australia

27th International Symposium on Algorithms and Computation (ISAAC 2016)



Seok-Hee Hong (Ed.)
ISBN 978-3-95977-026-2, LIPICS Vol. 64 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 31 MB)
Search Publication Server


Authors
  • Abdullah, Amirali
  • Abu-Khzam, Faisal
  • Agarwal, Pankaj K.
  • Agarwal, Udit
  • Agrawal, Akanksha
  • Ahn, Hee-Kap
  • Aichholzer, Oswin
  • Akitaya, Hugo A.
  • Alt, Helmut
  • Amir, Amihood
  • Angelini, Patrizio
  • Bae, Sang Won
  • Bandyapadhyay, Sayan
  • Bazgan, Cristina
  • Berndt, Sebastian
  • Biedl, Therese
  • Bille, Philip
  • Biniaz, Ahmad
  • Bodlaender, Hans L.
  • Böhm, Martin
  • Bose, Prosenjit
  • Casel, Katrin
  • Chakraborty, Sankardeep
  • Chan, T-H. Hubert
  • Chan, Timothy M.
  • Chen, Di
  • Chen, Ho-Lin
  • Chen, Lijie
  • Chrobak, Marek
  • Cording, Patrick Hagge
  • Czyzowicz, Jurek
  • Da Lozzo, Giordano
  • Daruki, Samira
  • De Carufel, Jean-Lou
  • Ding, Hu
  • Domanic, Nevzat Onur
  • Elmasry, Amr
  • El-Zein, Hicham
  • Etscheid, Michael
  • Fekete, Sándor P.
  • Feldmann, Andreas Emil
  • Fernau, Henning
  • Ganguly, Arnab
  • Gavoille, Cyril
  • Georgiou, Konstantinos
  • Ghandeharizadeh, Shahram
  • Golin, Mordecai
  • Gørtz, Inge Li
  • Hackl, Thomas
  • Ham, Lucy
  • Hoang, Duc A.
  • Hong, Seok-Hee
  • Hon, Wing-Kai
  • Huang, Ziyun
  • Irani, Sandy
  • Itsykson, Dmitry
  • Jez, Lukasz
  • Jin, Kai
  • Kammer, Frank
  • Kao, Mong-Jen
  • Kawase, Yasushi
  • Klavík, Pavel
  • Knop, Alexander
  • Kociumaka, Tomasz
  • Könemann, Jochen
  • Kontogiannis, Spyros
  • Kopelowitz, Tsvi
  • Korman, Matias
  • Kranakis, Evangelos
  • Krizanc, Danny
  • Kurz, Denis
  • Lam, Chi-Kit
  • Lam, Jenny
  • Lee, Der-Tsai
  • Lee, D. T.
  • Le, Hoang-Oanh
  • Le, Van Bang
  • Levy, Avivit
  • Li, Fei
  • Lin, Guohui
  • Lin, Tien-Ching
  • Lin, Xuemin
  • Li, Qian
  • Li, Shimin
  • Liskiewicz, Maciej
  • Liu, Fu-Hong
  • Liu, Hsiang-Hsuan
  • Liu, Yangwei
  • Löffler, Maarten
  • Luo, Wenchang
  • Maheshwari, Anil
  • Makino, Kazuhisa
  • Martin, Christopher S.
  • Matsui, Tomomi
  • Mehrabi, Saeed
  • Mitchell, Joseph S. B.
  • Miyauchi, Atsushi
  • Mnich, Matthias
  • Moriguchi, Satoko
  • Munro, J. Ian
  • Murota, Kazuo
  • Mutzel, Petra
  • Nagamochi, Hiroshi
  • Narayanan, Lata
  • Oh, Eunjin
  • Ono, Hirotaka
  • Opatrny, Jaroslav
  • Otachi, Yota
  • Pan, Jiangwei
  • Panolan, Fahad
  • Park, Kunsoo
  • Pashkovich, Kanstantsin
  • Pettie, Seth
  • Pilz, Alexander
  • Pissis, Solon P.
  • Plaxton, C. Gregory
  • Porat, Ely
  • Radoszewski, Jakub
  • Ramachandran, Vijaya
  • Raman, Venkatesh
  • Robertson, Matthew
  • Roeloffzen, Marcel
  • Rote, Günter
  • Roy, Chitradeep Dutta
  • Salavatipour, Mohammad R.
  • Sanità, Laura
  • Satti, Srinivasa Rao
  • Saurabh, Saket
  • Scharf, Nadja
  • Scheffer, Christian
  • Seimi, Kento
  • Šejnoha, Jiri
  • Sgall, Jirí
  • Shah, Rahul
  • Shalom, B. Riva
  • Sharma, Roohani
  • Shende, Sunil
  • Skjoldjensen, Frederik Rye
  • Skrepetos, Dimitrios
  • Smid, Michiel
  • Sokolov, Dmitry
  • Staals, Frank
  • Sun, Xiaoming
  • Tamura, Akihisa
  • Tang, Zhihao Gavin
  • Tardella, Fabio
  • Thankachan, Sharma V.
  • Tong, Weitian
  • Tóth, Csaba D.
  • Tu, Hai-Lun
  • Uehara, Ryuhei
  • Vahrenhold, Jan
  • van Kreveld, Marc
  • van Renssen, André
  • Varadarajan, Kasturi
  • Venkatasubramanian, Suresh
  • Veselý, Pavel
  • Victor, Will
  • Vildhøj, Hjalte Wedel
  • Vind, Søren
  • Vogtenhuber, Birgit
  • Wagner, Dorothea
  • Wang, Haitao
  • Wang, Te-Li
  • Wiratma, Lionov
  • Wong, Prudence W. H.
  • Wu, Xiaowei
  • Xiao, Mingyu
  • Xu, Jinhui
  • Xu, Yao
  • Yamaguchi, Yutaro
  • Yeh, Chih-Kuan
  • Yu, Hung-I
  • Zaroliagis, Christos
  • Zehavi, Meirav
  • Zhang, Jialin

  •   
    Front Matter, Table of Contents, Preface, Program Committee, External Reviewers
    Authors: Hong, Seok-Hee

    Abstract | Document (345 KB) | BibTeX

    Towards Processing of Big Graphs: from Theory, Algorithm to System (Invited Talk)
    Authors: Lin, Xuemin

    Abstract | Document (199 KB) | BibTeX

    Compressed and Searchable Indexes for Highly Similar Strings (Invited Talk)
    Authors: Park, Kunsoo

    Abstract | Document (237 KB) | BibTeX

    Streaming Verification of Graph Properties
    Authors: Abdullah, Amirali ; Daruki, Samira ; Roy, Chitradeep Dutta ; Venkatasubramanian, Suresh

    Abstract | Document (768 KB) | BibTeX

    Building Clusters with Lower-Bounded Sizes
    Authors: Abu-Khzam, Faisal ; Bazgan, Cristina ; Casel, Katrin ; Fernau, Henning

    Abstract | Document (500 KB) | BibTeX

    Simultaneous Feedback Edge Set: A Parameterized Perspective
    Authors: Agrawal, Akanksha ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (602 KB) | BibTeX

    Kernels for Deletion to Classes of Acyclic Digraphs
    Authors: Agrawal, Akanksha ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

    Abstract | Document (526 KB) | BibTeX

    An Efficient Algorithm for Placing Electric Vehicle Charging Stations
    Authors: Agarwal, Pankaj K. ; Pan, Jiangwei ; Victor, Will

    Abstract | Document (520 KB) | BibTeX

    Finding k Simple Shortest Paths and Cycles
    Authors: Agarwal, Udit ; Ramachandran, Vijaya

    Abstract | Document (494 KB) | BibTeX

    Packing Short Plane Spanning Trees in Complete Geometric Graphs
    Authors: Aichholzer, Oswin ; Hackl, Thomas ; Korman, Matias ; Pilz, Alexander ; Rote, Günter ; van Renssen, André ; Roeloffzen, Marcel ; Vogtenhuber, Birgit

    Abstract | Document (565 KB) | BibTeX

    Reconstruction of Weakly Simple Polygons from their Edges
    Authors: Akitaya, Hugo A. ; Tóth, Csaba D.

    Abstract | Document (548 KB) | BibTeX

    Approximating Smallest Containers for Packing Three-Dimensional Convex Objects
    Authors: Alt, Helmut ; Scharf, Nadja

    Abstract | Document (603 KB) | BibTeX

    Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
    Authors: Amir, Amihood ; Kopelowitz, Tsvi ; Levy, Avivit ; Pettie, Seth ; Porat, Ely ; Shalom, B. Riva

    Abstract | Document (509 KB) | BibTeX

    Clustered Planarity with Pipes
    Authors: Angelini, Patrizio ; Da Lozzo, Giordano

    Abstract | Document (685 KB) | BibTeX

    L_1 Geodesic Farthest Neighbors in a Simple Polygon and Related Problems
    Authors: Bae, Sang Won

    Abstract | Document (599 KB) | BibTeX

    Approximate Clustering via Metric Partitioning
    Authors: Bandyapadhyay, Sayan ; Varadarajan, Kasturi

    Abstract | Document (485 KB) | BibTeX

    Hard Communication Channels for Steganography
    Authors: Berndt, Sebastian ; Liskiewicz, Maciej

    Abstract | Document (532 KB) | BibTeX

    On r-Guarding Thin Orthogonal Polygons
    Authors: Biedl, Therese ; Mehrabi, Saeed

    Abstract | Document (541 KB) | BibTeX

    Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
    Authors: Bille, Philip ; Cording, Patrick Hagge ; Gørtz, Inge Li ; Skjoldjensen, Frederik Rye ; Vildhøj, Hjalte Wedel ; Vind, Søren

    Abstract | Document (504 KB) | BibTeX

    Towards Plane Spanners of Degree 3
    Authors: Biniaz, Ahmad ; Bose, Prosenjit ; De Carufel, Jean-Lou ; Gavoille, Cyril ; Maheshwari, Anil ; Smid, Michiel

    Abstract | Document (672 KB) | BibTeX

    Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity
    Authors: Bodlaender, Hans L. ; Ono, Hirotaka ; Otachi, Yota

    Abstract | Document (525 KB) | BibTeX

    Online Packet Scheduling with Bounded Delay and Lookahead
    Authors: Böhm, Martin ; Chrobak, Marek ; Jez, Lukasz ; Li, Fei ; Sgall, Jirí ; Veselý, Pavel

    Abstract | Document (589 KB) | BibTeX

    Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits
    Authors: Chakraborty, Sankardeep ; Raman, Venkatesh ; Satti, Srinivasa Rao

    Abstract | Document (453 KB) | BibTeX

    On (1, epsilon)-Restricted Max-Min Fair Allocation Problem
    Authors: Chan, T-H. Hubert ; Tang, Zhihao Gavin ; Wu, Xiaowei

    Abstract | Document (553 KB) | BibTeX

    All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time
    Authors: Chan, Timothy M. ; Skrepetos, Dimitrios

    Abstract | Document (485 KB) | BibTeX

    Sink Evacuation on Trees with Dynamic Confluent Flows
    Authors: Chen, Di ; Golin, Mordecai

    Abstract | Document (541 KB) | BibTeX

    Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation
    Authors: Chen, Lijie

    Abstract | Document (601 KB) | BibTeX

    Search on a Line by Byzantine Robots
    Authors: Czyzowicz, Jurek ; Georgiou, Konstantinos ; Kranakis, Evangelos ; Krizanc, Danny ; Narayanan, Lata ; Opatrny, Jaroslav ; Shende, Sunil

    Abstract | Document (467 KB) | BibTeX

    Bipartite Matching with Linear Edge Weights
    Authors: Domanic, Nevzat Onur ; Lam, Chi-Kit ; Plaxton, C. Gregory

    Abstract | Document (416 KB) | BibTeX

    Raising Permutations to Powers in Place
    Authors: El-Zein, Hicham ; Munro, J. Ian ; Robertson, Matthew

    Abstract | Document (499 KB) | BibTeX

    Space-Efficient Plane-Sweep Algorithms
    Authors: Elmasry, Amr ; Kammer, Frank

    Abstract | Document (419 KB) | BibTeX

    Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
    Authors: Etscheid, Michael ; Mnich, Matthias

    Abstract | Document (549 KB) | BibTeX

    Universal Guard Problems
    Authors: Fekete, Sándor P. ; Li, Qian ; Mitchell, Joseph S. B. ; Scheffer, Christian

    Abstract | Document (670 KB) | BibTeX

    Fast Approximation Algorithms for the Generalized Survivable Network Design Problem
    Authors: Feldmann, Andreas Emil ; Könemann, Jochen ; Pashkovich, Kanstantsin ; Sanità, Laura

    Abstract | Document (522 KB) | BibTeX

    Space-Time Trade-Offs for the Shortest Unique Substring Problem
    Authors: Ganguly, Arnab ; Hon, Wing-Kai ; Shah, Rahul ; Thankachan, Sharma V.

    Abstract | Document (534 KB) | BibTeX

    The Subset Assignment Problem for Data Placement in Caches
    Authors: Ghandeharizadeh, Shahram ; Irani, Sandy ; Lam, Jenny

    Abstract | Document (545 KB) | BibTeX

    A Gap Trichotomy for Boolean Constraint Problems: Extending Schaefer's Theorem
    Authors: Ham, Lucy

    Abstract | Document (503 KB) | BibTeX

    Sliding Tokens on a Cactus
    Authors: Hoang, Duc A. ; Uehara, Ryuhei

    Abstract | Document (761 KB) | BibTeX

    Complexity of Distributions and Average-Case Hardness
    Authors: Itsykson, Dmitry ; Knop, Alexander ; Sokolov, Dmitry

    Abstract | Document (473 KB) | BibTeX

    Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach
    Authors: Jin, Kai

    Abstract | Document (461 KB) | BibTeX

    O(f) Bi-Approximation for Capacitated Covering with Hard Capacities
    Authors: Kao, Mong-Jen ; Tu, Hai-Lun ; Lee, D. T.

    Abstract | Document (516 KB) | BibTeX

    Surrogate Optimization for p-Norms
    Authors: Kawase, Yasushi ; Makino, Kazuhisa

    Abstract | Document (522 KB) | BibTeX

    Optimal Composition Ordering Problems for Piecewise Linear Functions
    Authors: Kawase, Yasushi ; Makino, Kazuhisa ; Seimi, Kento

    Abstract | Document (433 KB) | BibTeX

    Additive Approximation Algorithms for Modularity Maximization
    Authors: Kawase, Yasushi ; Matsui, Tomomi ; Miyauchi, Atsushi

    Abstract | Document (1,053 KB) | BibTeX

    The Densest Subgraph Problem with a Convex/Concave Size Function
    Authors: Kawase, Yasushi ; Miyauchi, Atsushi

    Abstract | Document (519 KB) | BibTeX

    On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
    Authors: Klavík, Pavel ; Otachi, Yota ; Šejnoha, Jiri

    Abstract | Document (533 KB) | BibTeX

    Pattern Matching and Consensus Problems on Weighted Sequences and Profiles
    Authors: Kociumaka, Tomasz ; Pissis, Solon P. ; Radoszewski, Jakub

    Abstract | Document (556 KB) | BibTeX

    Hierarchical Time-Dependent Oracles
    Authors: Kontogiannis, Spyros ; Wagner, Dorothea ; Zaroliagis, Christos

    Abstract | Document (693 KB) | BibTeX

    A Refined Definition for Groups of Moving Entities and its Computation
    Authors: van Kreveld, Marc ; Löffler, Maarten ; Staals, Frank ; Wiratma, Lionov

    Abstract | Document (535 KB) | BibTeX

    A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph
    Authors: Kurz, Denis ; Mutzel, Petra

    Abstract | Document (538 KB) | BibTeX

    On the Complexity of Matching Cut in Graphs of Fixed Diameter
    Authors: Le, Hoang-Oanh ; Le, Van Bang

    Abstract | Document (477 KB) | BibTeX

    On the Optimality of Tape Merge of Two Lists with Similar Size
    Authors: Li, Qian ; Sun, Xiaoming ; Zhang, Jialin

    Abstract | Document (501 KB) | BibTeX

    Dispersing Points on Intervals
    Authors: Li, Shimin ; Wang, Haitao

    Abstract | Document (592 KB) | BibTeX

    Optimal Nonpreemptive Scheduling in a Smart Grid Model
    Authors: Liu, Fu-Hong ; Liu, Hsiang-Hsuan ; Wong, Prudence W. H.

    Abstract | Document (551 KB) | BibTeX

    Distributed and Robust Support Vector Machine
    Authors: Liu, Yangwei ; Ding, Hu ; Huang, Ziyun ; Xu, Jinhui

    Abstract | Document (1,968 KB) | BibTeX

    Single Machine Scheduling with Job-Dependent Machine Deterioration
    Authors: Luo, Wenchang ; Xu, Yao ; Tong, Weitian ; Lin, Guohui

    Abstract | Document (497 KB) | BibTeX

    Approximation Algorithms for Capacitated k-Travelling Repairmen Problems
    Authors: Martin, Christopher S. ; Salavatipour, Mohammad R.

    Abstract | Document (502 KB) | BibTeX

    Scaling and Proximity Properties of Integrally Convex Functions
    Authors: Moriguchi, Satoko ; Murota, Kazuo ; Tamura, Akihisa ; Tardella, Fabio

    Abstract | Document (527 KB) | BibTeX

    Assigning Weights to Minimize the Covering Radius in the Plane
    Authors: Oh, Eunjin ; Ahn, Hee-Kap

    Abstract | Document (452 KB) | BibTeX

    A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree
    Authors: Oh, Eunjin ; Ahn, Hee-Kap

    Abstract | Document (575 KB) | BibTeX

    Approximate Shortest Distances Among Smooth Obstacles in 3D
    Authors: Scheffer, Christian ; Vahrenhold, Jan

    Abstract | Document (557 KB) | BibTeX

    An Improved Tax Scheme for Selfish Routing
    Authors: Wang, Te-Li ; Yeh, Chih-Kuan ; Chen, Ho-Lin

    Abstract | Document (478 KB) | BibTeX

    A Linear-Time Algorithm for Integral Multiterminal Flows in Trees
    Authors: Xiao, Mingyu ; Nagamochi, Hiroshi

    Abstract | Document (604 KB) | BibTeX

    Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity
    Authors: Yamaguchi, Yutaro

    Abstract | Document (408 KB) | BibTeX

    The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints
    Authors: Yu, Hung-I ; Lin, Tien-Ching ; Lee, Der-Tsai

    Abstract | Document (458 KB) | BibTeX

      




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