Portal - ISAAC 2016

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

Chakraborty, Sankardeep

Cording, Patrick Hagge

Feldmann, Andreas Emil

Fernau, Henning

Ganguly, Arnab

Gavoille, Cyril

Georgiou, Konstantinos

Ghandeharizadeh, Shahram

Martin, Christopher S.

Matsui, Tomomi

Mehrabi, Saeed

Mitchell, Joseph S. B.

Pashkovich, Kanstantsin

Roy, Chitradeep Dutta

Salavatipour, Mohammad R.

Skjoldjensen, Frederik Rye

Thankachan, Sharma V.

Venkatasubramanian, Suresh

Veselý, Pavel

Victor, Will

Vildhøj, Hjalte Wedel

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

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