ISAAC 2014 Accepted Papers

Prosenjit Bose, Pat Morin and Andre van Renssen. The Price of Order
Xingfu Li and Daming Zhu. Approximating Maximum Internal Spanning Tree Via Maximum Path-Cycle Cover
Ken Fong, Minming Li, Hongyu Liang, Linji Yang and Hao Yuan. Average-Case Complexity of the Min-Sum Matrix Product Problem
Jesper Jansson, Wing-Kin Sung, Hoa Vu and S.M. Yiu. Faster Algorithms for Computing the R* Consensus Tree
Mingyu Xiao and Hiroshi Nagamochi. Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
Prosenjit Bose, Karim Douieb, John Iacono and Stefan Langerman. The Power and Limitations of Static Binary Search Trees with Lazy Finger
Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui and Ryuhei Uehara. Depth-First Search Using O(n) bits
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto. Minimum-Cost b-Edge Dominating Sets on Trees
Jian Li and Haitao Wang. Range Queries on Uncertain Data
Weitian Tong and Guohui Lin. An Improved Approximation Algorithm for the Minimum Common Integer Partition Problem
Andre Droschinsky, Bernhard Heinemann, Nils Kriege and Petra Mutzel. Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
Daniel Kane and Osamu Watanabe. A Short Implicant of a CNF Formula with Many Satisfying Assignments
Bakhadyr Khoussainov, Mikhail Kokho, Jiamou Liu and Alexander Gavruskin. Dynamic Interval Scheduling for Multiple Machines
Tomomi Matsui, Yukihide Kohira, Chikaaki Kodama and Atsushi Takahashi. Positive Semidefinite Relaxation and Approximation Algorithm for Triple Patterning Lithography
Haitao Wang and Jingru Zhang. Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
Pavel Kolev and He Sun. Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs
Leszek Gasieniec, Christos Levcopoulos and Andrzej Lingas. Efficiently Correcting Matrix Products
Zhanpeng Cheng and David Eppstein. Linear-time Algorithms for Proportional Apportionment
Pawel Gawrychowski and Damian Rusak. Euclidean TSP with few inner points in linear space
Meghana Nasre, Matteo Pontecorvi and Vijaya Ramachandran. Decremenal ALL-Pairs ALL Shortest Paths and Betweenness Centrality.
Therese Biedl, Stefan Huber and Peter Palfrader. Planar Matchings for Weighted Straight Skeletons
Paal Groenaas Drange, Markus Sortland Dregi and Pim van 'T Hof. On the Computational Complexity of Vertex Integrity and Component Order Connectivity
Amer Mouawad, Naomi Nishimura and Venkatesh Raman. Vertex Cover Reconfiguration and Beyond
Oswin Aichholzer, Jean Cardinal, Vincent Kusters, Stefan Langerman and Pavel Valtr. Reconstructing Point Set Order Types from Radial Orderings
Laurent Bulteau, Vincent Froese, Sepp Hartung and Rolf Niedermeier. Co-Clustering Under the Maximum Norm
Pratik Ghosal, Meghana Nasre and Prajakta Nimbhorkar. Rank-Maximal Matchings - Structure and Algorithms
Subhash Suri and Kevin Verbeek. On the Most Likely Voronoi Diagram and Nearest Neighbor Searching
Meng He, Ganggui Tang and Norbert Zeh. Orienting Dynamic Graphs, With Applications to Maximal Matchings and Adjacency Queries
Pavel Klavik and Maria Saumell. Minimal Obstructions for Partial Representations of Interval Graphs
Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang and Kun-Mao Chao. The Generalized Popular Condensation Problem
Norman Huang and Allan Borodin. Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization
Kunihiro Wasa, Hiroki Arimura and Takeaki Uno. Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
Ei Ando and Shuji Kijima. An FPTAS for The Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution Integral
Jan Obdrzalek, Petr Hlineny, Sebastian Ordyniak and Jakub Gajarsky. Faster Existential FO Model Checking on Posets
Peter Floderus, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas and Dzmitry Sledneu. 3D rectangulations and geometric matrix multiplication
Alberto Policriti and Nicola Prezza. Hashing and Indexing: succinct data structures and smoothed analysis
Rafel Jaume and Matthias Henze. Bottleneck Partial-Matching Voronoi Diagrams and Applications
Shashank Mehta and Pawan Aurora. A Geometric Approach to Graph Isomorphism
Stefan Felsner and Alexander Pilz. Ham-Sandwich Cuts for Abstract Order Types
Giordano Da Lozzo, Vit Jelinek, Jan Kratochvil and Ignaz Rutter. Planar Embeddings with Small and Uniform Faces
Cecilia Bohler, Chih-Hung Liu, Evanthia Papadopoulou and Maksym Zavershynskyi. A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams
Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen. Covering Problems for Partial Words and for Indeterminate Strings
Eric Angel, Evripidis Bampis, Vincent Chau and Kim Thang Nguyen. Throughput Maximization in Multiprocessor Speed-Scaling
Per Kristian Lehre and Carsten Witt. Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift
Yuma Inoue and Shin-Ichi Minato. An Efficient Method for Indexing All Topological Orders of a Directed Graph
Ashwin Arulselvan, Martin Groß and Martin Skutella. Graph Orientation and Flows Over Time
Nevzat Onur Domanic and C. Gregory Plaxton. Scheduling Unit Jobs with a Common Deadline to Minimize the Sum of Weighted Completion Times and Rejection Penalties
Hicham El-Zein, Ian Munro and Venkatesh Raman. Tradeoff between label space and auxiliary space for representation of equivalence classes
Noy Rotbart, Søren Dahlgaard and Mathias Bæk Tejs Knudsen. Dynamic and Multi-functional Labeling Schemes
Evripidis Bampis, Dimitrios Letsios and Giorgio Lucarelli. Speed-scaling with no Preemptions
Faisal Abu-Khzam, Cristina Bazgan, Morgan Chopin and Henning Fernau. Approximation Algorithms Inspired by Kernelization Methods
Gonzalo Navarro, Ian Munro, Jesper Sindahl Nielsen, Rahul Shah and Sharma V. Thankachan. Top-k Term-Proximity in Succinct Space
Erik D. Demaine, Martin Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara and Takeshi Yamada. Polynomial-Time Algorithm for Sliding Tokens on Trees
Haitao Jiang, Haodi Feng and Daming Zhu. An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
Xiaoming Sun, Jia Zhang and Jialin Zhang. Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol
Takehiro Ito, Marcin Kami?ski and Hirotaka Ono. Fixed-Parameter Tractability of Token Jumping on Planar Graphs
Grzegorz Gutowski, Jakub Kozik, Piotr Micek and Xuding Zhu. Lower Bounds for On-line Graph Colorings
Ruben Becker and Andreas Karrenbauer. A Simple Efficient Interior Point Method for Min-Cost Flow
Meng He, J. Ian Munro and Gelin Zhou. Dynamic Path Counting and Reporting in Linear Space
Piotr Micek and Veit Wiechert. On-line competitive coloring algorithms for bipartite graphs without long induced paths