Download: Program.pdf
Online version of the ISAAC 2014 conference proceedings on SpringerLink: LNCS 2014 "Algorithms and Computation"
Welcome reception : 6pm, 14 December at Jeonju Traditional Culture Center, the conference venue.

Day 1 (December 15) - ISAAC 2014

Session A (Hanbyeok theater) Session B (Gyeongopdang)
09:00-10:00 Invited Talk 1: Biconnectivity in Directed Graphs. Giuseppe F. Italiano / Chair: Kunsoo Park
10:00-10:30 Coffee Break
Session 1
Computational Geometry I / Helmut Alt Combinatorial Optimization I / Sang Won Bae

Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane. Haitao Wang and Jingru Zhang

Average-Case Complexity of the Min-Sum Matrix Product Problem. Ken Fong, Minming Li, Hongyu Liang, Linji Yang and Hao Yuan

Reconstructing Point Set Order Types from Radial Orderings. Oswin Aichholzer, Jean Cardinal, Vincent Kusters, Stefan Langerman and Pavel Valtr

Efficiently Correcting Matrix Products. Leszek Gąsieniec, Christos Levcopoulos and Andrzej Lingas

A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams. Cecilia Bohler, Chih-Hung Liu, Evanthia Papadopoulou and Maksym Zavershynskyi

3D rectangulations and geometric matrix multiplication. Peter Floderus, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas and Dzmitry Sledneu
11:45-13:30 Lunch
Session 2
Graph Algorithms: Enumeration / Ryuhei Uehara Matching and Assignment I / Kun-Mao Chao

Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay. Andre Droschinsky, Bernhard Heinemann, Nils Kriege and Petra Mutzel

Planar Matchings for Weighted Straight Skeletons. Therese Biedl, Stefan Huber and Peter Palfrader

Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph. Kunihiro Wasa, Hiroki Arimura and Takeaki Uno

Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries. Meng He, Ganggui Tang and Norbert Zeh

An Efficient Method for Indexing All Topological Orders of a Directed Graph. Yuma Inoue and Shin-Ichi Minato

Dynamic and Multi-functional Labeling Schemes. Søren Dahlgaard, Mathias Bæk Tejs Knudsen and Noy Rotbart
14:45-15:05 Coffee Break
Session 3
Data Structures and Algorithms I / Meng He Fixed-Parameter Tractable Algorithms I / Mingyu Xiao

Hashing and Indexing: succinct data structures and smoothed analysis Alberto Policriti and Nicola Prezza

Minimum-Cost b-Edge Dominating Sets on Trees. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto

Top-k Term-Proximity in Succinct Space. J. Ian Munro, Gonzalo Navarro, Jesper Sindahl Nielsen, Rahul Shah and Sharma V. Thankachan

Fixed-Parameter Tractability of Token Jumping on Planar Graphs. Takehiro Ito, Marcin Kamiński and Hirotaka Ono

The Power and Limitations of Static Binary Search Trees with Lazy Finger. Prosenjit Bose, Karim Douieb, John Iacono and Stefan Langerman

Covering Problems for Partial Words and for Indeterminate Strings. Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
16:20-16:40 Coffee Break
Session 4
Scheduling Algorithms / Francis Chin Computational Complexity / Inbok Lee

Dynamic Interval Scheduling for Multiple Machines. Alexander Gavruskin, Bakhadyr Khoussainov, Mikhail Kokho and Jiamou Liu

A Short Implicant of a CNF Formula with Many Satisfying Assignments. Daniel M. Kane and Osamu Watanabe

Throughput Maximization in Multiprocessor Speed-Scaling. Eric Angel, Evripidis Bampis, Vincent Chau and Kim Thang Nguyen

On the Computational Complexity of Vertex Integrity and Component Order Connectivity. Pal Grønas Drange, Markus Sortland Dregi and Pim van 't Hof

Speed-scaling with no Preemptions. Evripidis Bampis, Dimitrios Letsios and Giorgio Lucarelli

Co-Clustering Under the Maximum Norm. Laurent Bulteau, Vincent Froese, Sepp Hartung and Rolf Niedermeier

Day 2 (December 16) - ISAAC 2014

Session A (Hanbyeok theater) Session B (Gyeongopdang)
09:00-10:00 Invited Talk 2: Social Network Algorithmics. Ulrik Brandes / Chair: Takeshi Tokuyama
10:00-10:30 Coffee Break
Session 5
Computational Geometry II / D. T. Lee Approximation Algorithms / Jinhee Chun

The Price of Order. Prosenjit Bose, Pat Morin and Andre van Renssen

An Improved Approximation Algorithm for the Minimum Common Integer Partition Problem. Weitian Tong and Guohui Lin

Range Queries on Uncertain Data. Jian Li and Haitao Wang

Positive Semidefinite Relaxation and Approximation Algorithm for Triple Patterning Lithography. Tomomi Matsui, Yukihide Kohira, Chikaaki Kodama and Atsushi Takahashi

On the Most Likely Voronoi Diagram and Nearest Neighbor Searching. Subhash Suri and Kevin Verbeek

An FPTAS for The Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution Integral. Ei Ando and Shuji Kijima
11:45-13:30 Lunch
Session 6
Graph Theory and Algorithms / Stefan Felsner Fixed-Parameter Tractable Algorithms II / Yoshio Okamoto

Polynomial-Time Algorithm for Sliding Tokens on Trees. Erik D. Demaine, Martin Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara and Takeshi Yamada

Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs. Mingyu Xiao and Hiroshi Nagamochi

Minimal Obstructions for Partial Representations of Interval Graphs. Pavel Klavik and Maria Saumell

Vertex Cover Reconfiguration and Beyond. Amer E. Mouawad, Naomi Nishimura and Venkatesh Raman

Faster Algorithms for Computing the R* Consensus Tree. Jesper Jansson, Wing-Kin Sung, Hoa Vu and Siu-Ming Yiu

Faster Existential FO Model Checking on Posets. Jakub Gajarsky, Petr Hliněny, Jan Obdržalek and Sebastian Ordyniak
14:45-15:05 Coffee Break
Session 7
Graph Algorithms: Approximation I / Petr Hliněny Online and Approximation Algorithms / Hirotaka Ono

Approximating the Maximum Internal Spanning Tree Via a Maximum Path-Cycle Cover. Xingfu Li and Daming Zhu

Lower Bounds for On-line Graph Colorings. Grzegorz Gutowski, Jakub Kozik, Piotr Micek and Xuding Zhu

Approximation Algorithms Inspired by Kernelization Methods. Faisal Abu-Khzam, Cristina Bazgan, Morgan Chopin and Henning Fernau

An On-line Competitive Algorithm for Coloring P8-free Bipartite Graphs. Piotr Micek and Veit Wiechert

An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves. Haitao Jiang, Haodi Feng and Daming Zhu

Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization. Norman Huang and Allan Borodin
16:20-16:40 Coffee Break
16:40-17:30 Korean Traditional Performance
17:30-18:30 ISAAC, a Quarter of a Century
18:30-20:00 Banquet

Day 3 (December 17) - ISAAC 2014

Session A (Hanbyeok theater) Session B (Gyeongopdang)
Session 8
Data Structures and Algorithms II / Osamu Watanabe Matching and Assignment II / Yo-Sub Han

Tradeoff between label space and auxiliary space for representation of equivalence classes. Hicham El-Zein, J. Ian Munro and Venkatesh Raman

Linear-time Algorithms for Proportional Apportionment. Zhanpeng Cheng and David Eppstein

Depth-First Search Using O(n) bits. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui and Ryuhei Uehara

Rank-Maximal Matchings - Structure and Algorithms. Pratik Ghosal, Meghana Nasre and Prajakta Nimbhorkar

Dynamic Path Counting and Reporting in Linear Space. Meng He, J. Ian Munro and Gelin Zhou

The Generalized Popular Condensation Problem. Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang and Kun-Mao Chao
10:15-10:35 Coffee Break
Session 9
Graph Algorithms: Approximation II / Chan-Su Shin Combinatorial Optimization II / Andrzej Lingas

Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs. Pavel Kolev and He Sun

Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol. Xiaoming Sun, Jia Zhang and Jialin Zhang

Planar Embeddings with Small and Uniform Faces. Giordano Da Lozzo, Vit Jelinek, Jan Kratochvil and Ignaz Rutter

A Geometric Approach to Graph Isomorphism. Pawan Aurora and Shashank Mehta

Scheduling Unit Jobs with a Common Deadline to Minimize the Sum of Weighted Completion Times and Rejection Penalties. Nevzat Onur Domanic and C. Gregory Plaxton

Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift. Per Kristian Lehre and Carsten Witt
11:50-13:30 Lunch
Session 10
Computational Geometry III / Evanthia Papadopoulou Network and Scheduling Algorithms / Hee-Kap Ahn

Euclidean TSP with few inner points in linear space. Pawel Gawrychowski and Damian Rusak

Graph Orientation and Flows Over Time. Ashwin Arulselvan, Martin Groß and Martin Skutella

Bottleneck Partial-Matching Voronoi Diagrams and Applications. Matthias Henze and Rafel Jaume

A Simple Efficient Interior Point Method for Min-Cost Flow. Ruben Becker and Andreas Karrenbauer

Ham-Sandwich Cuts for Abstract Order Types. Stefan Felsner and Alexander Pilz

Decremental ALL-Pairs ALL Shortest Paths and Betweenness Centrality. Meghana Nasre, Matteo Pontecorvi and Vijaya Ramachandran