Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings

Front Matter....Pages I-XXII
Front Matter....Pages 1-1
Line-Constrained $$k$$ -Median, $$k$$ -Means, and $$k$$ -Center Problems in the Plane....Pages 3-14
Reconstructing Point Set Order Typesfrom Radial Orderings....Pages 15-26
A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams....Pages 27-37
Front Matter....Pages 39-39
Average-Case Complexity of the Min-Sum Matrix Product Problem....Pages 41-52
Efficiently Correcting Matrix Products....Pages 53-64
3D Rectangulations and Geometric Matrix Multiplication....Pages 65-78
Front Matter....Pages 79-79
Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay....Pages 81-93
Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph....Pages 94-102
An Efficient Method for Indexing All Topological Orders of a Directed Graph....Pages 103-114
Front Matter....Pages 115-115
Planar Matchings for Weighted Straight Skeletons....Pages 117-127
Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries....Pages 128-140
Dynamic and Multi-Functional Labeling Schemes....Pages 141-153
Front Matter....Pages 155-155
Hashing and Indexing: Succinct DataStructures and Smoothed Analysis....Pages 157-168
Top- $$k$$ Term-Proximity in Succinct Space....Pages 169-180
The Power and Limitations of Static Binary Search Trees with Lazy Finger....Pages 181-192
Front Matter....Pages 193-193
Minimum-Cost $$b$$ -Edge Dominating Sets on Trees....Pages 195-207
Fixed-Parameter Tractability of Token Jumping on Planar Graphs....Pages 208-219
Covering Problems for Partial Words and for Indeterminate Strings....Pages 220-232
Front Matter....Pages 233-233
Dynamic Interval Scheduling for Multiple Machines....Pages 235-246
Throughput Maximization in Multiprocessor Speed-Scaling....Pages 247-258
Front Matter....Pages 233-233
Speed-Scaling with No Preemptions....Pages 259-269
Front Matter....Pages 271-271
A Short Implicant of a CNF Formula with Many Satisfying Assignments....Pages 273-284
On the Computational Complexity of Vertex Integrity and Component Order Connectivity....Pages 285-297
Co-Clustering Under the Maximum Norm....Pages 298-309
Front Matter....Pages 311-311
The Price of Order....Pages 313-325
Range Queries on Uncertain Data....Pages 326-337
On the Most Likely Voronoi Diagramand Nearest Neighbor Searching....Pages 338-350
Front Matter....Pages 351-351
An Improved Approximation Algorithm for the Minimum Common Integer Partition Problem....Pages 353-364
Positive Semidefinite Relaxation and Approximation Algorithm for Triple Patterning Lithography....Pages 365-375
An FPTAS for the Volume Computationof 0-1 Knapsack Polytopes Based on Approximate Convolution Integral....Pages 376-386
Front Matter....Pages 387-387
Polynomial-Time Algorithm for Sliding Tokens on Trees....Pages 389-400
Minimal Obstructions for Partial Representations of Interval Graphs....Pages 401-413
Faster Algorithms for Computing the R* Consensus Tree....Pages 414-425
Front Matter....Pages 427-427
Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs....Pages 429-440
Faster Existential FO Model Checking on Posets....Pages 441-451
Vertex Cover Reconfiguration and Beyond....Pages 452-463
Front Matter....Pages 465-465
Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover....Pages 467-478
Approximation Algorithms Inspired by Kernelization Methods....Pages 479-490
An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves....Pages 491-503
Front Matter....Pages 505-505
Lower Bounds for On-line Graph Colorings....Pages 507-515
Front Matter....Pages 505-505
An On-line Competitive Algorithm for Coloring $$P_8$$ -free Bipartite Graphs....Pages 516-527
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization....Pages 528-539
Front Matter....Pages 541-541
Tradeoff Between Label Space and Auxiliary Space for Representation of Equivalence Classes....Pages 543-552
Depth-First Search Using $$O(n)$$ Bits....Pages 553-564
Dynamic Path Counting and Reporting in Linear Space....Pages 565-577
Front Matter....Pages 579-579
Linear-Time Algorithms for Proportional Apportionment....Pages 581-592
Rank-Maximal Matchings – Structure and Algorithms....Pages 593-605
The Generalized Popular Condensation Problem....Pages 606-617
Front Matter....Pages 619-619
Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs....Pages 621-632
Planar Embeddings with Small and Uniform Faces....Pages 633-645
Scheduling Unit Jobs with a Common Deadline to Minimize the Sum of Weighted Completion Times and Rejection Penalties....Pages 646-657
Front Matter....Pages 659-659
Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol....Pages 661-673
A Geometric Approach to Graph Isomorphism....Pages 674-685
Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift....Pages 686-697
Front Matter....Pages 699-699
Euclidean TSP with Few Inner Points in Linear Space....Pages 701-713
Bottleneck Partial-Matching Voronoi Diagrams and Applications....Pages 714-725
Ham-Sandwich Cuts for Abstract Order Types....Pages 726-737
Front Matter....Pages 739-739
Graph Orientation and Flows over Time....Pages 741-752
A Simple Efficient Interior Point Method for Min-Cost Flow....Pages 753-765
Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality....Pages 766-778
Back Matter....Pages 779-781