Algorithms and Computation

1. Front Matter

   Pages I-XXII

   PDF

2. Computational Geometry

   1. Front Matter

      Pages 1-1

      PDF

   2. Line-Constrained \(k\)-Median, \(k\)-Means, and \(k\)-Center Problems in the Plane

      • Haitao Wang, Jingru Zhang

      Pages 3-14

   3. Reconstructing Point Set Order Typesfrom Radial Orderings

      • Oswin Aichholzer, Jean Cardinal, Vincent Kusters, Stefan Langerman, Pavel Valtr

      Pages 15-26

   4. A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams

      • Cecilia Bohler, Chih-Hung Liu, Evanthia Papadopoulou, Maksym Zavershynskyi

      Pages 27-37

3. Combinatorial Optimization

   1. Front Matter

      Pages 39-39

      PDF

   2. Average-Case Complexity of the Min-Sum Matrix Product Problem

      • Ken Fong, Minming Li, Hongyu Liang, Linji Yang, Hao Yuan

      Pages 41-52

   3. Efficiently Correcting Matrix Products

      • Leszek Gąsieniec, Christos Levcopoulos, Andrzej Lingas

      Pages 53-64

   4. 3D Rectangulations and Geometric Matrix Multiplication

      • Peter Floderus, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas, Dzmitry Sledneu

      Pages 65-78

4. Graph Algorithms: Enumeration

   1. Front Matter

      Pages 79-79

      PDF

   2. Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay

      • Andre Droschinsky, Bernhard Heinemann, Nils Kriege, Petra Mutzel

      Pages 81-93

   3. Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph

      • Kunihiro Wasa, Hiroki Arimura, Takeaki Uno

      Pages 94-102

   4. An Efficient Method for Indexing All Topological Orders of a Directed Graph

      • Yuma Inoue, Shin-ichi Minato

      Pages 103-114

5. Matching and Assignment

   1. Front Matter

      Pages 115-115

      PDF

   2. Planar Matchings for Weighted Straight Skeletons

      • Therese Biedl, Stefan Huber, Peter Palfrader

      Pages 117-127

   3. Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries

      • Meng He, Ganggui Tang, Norbert Zeh

      Pages 128-140

   4. Dynamic and Multi-Functional Labeling Schemes

      • Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart

      Pages 141-153

6. Data Structures and Algorithms

   1. Front Matter

      Pages 155-155

      PDF

   2. Hashing and Indexing: Succinct DataStructures and Smoothed Analysis

      • Alberto Policriti, Nicola Prezza

      Pages 157-168

   3. Top-\(k\) Term-Proximity in Succinct Space

      • J. Ian Munro, Gonzalo Navarro, Jesper Sindahl Nielsen, Rahul Shah, Sharma V. Thankachan

      Pages 169-180

This book constitutes the refereed proceedings of the 25th International Symposium on Algorithms and Computation, ISAAC 2014, held in Jeonju, Korea, in December 2014.
The 60 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 171 submissions for inclusion in the book. The focus of the volume in on the following topics: computational geometry, combinatorial optimization, graph algorithms: enumeration, matching and assignment, data structures and algorithms, fixed-parameter tractable algorithms, scheduling algorithms, computational complexity, computational complexity, approximation algorithms, graph theory and algorithms, online and approximation algorithms, and network and scheduling algorithms.

• Algorithmic Game Theory
• Algorithms
• Approximation
• Approximation Algorithms
• Combinatorial Optimization
• Computational Biology
• Computational Complexity
• Computational Geometry
• Cryptography
• Data Structures
• Distributed Algorithms
• Experimental Algorithms
• Graph Algorithms
• Graph Drawing
• Internet Algorithms
• Online Algorithms
• Parallel Algorithms
• Polynomial Time
• Quantum Computing
• Randomized Algorithms
• algorithm analysis and problem complexity

• Pohang University of Science and Technology, Pohang, Korea, Republic of (South Korea)

  Hee-Kap Ahn

• Hankuk University of Foreign Studies, Yongin-si, Korea, Republic of (South Korea)

  Chan-Su Shin

Policies and ethics