This book constitutes the refereed proceedings of the 19th International Symposium on Algorithms and Computation, ISAAC 2008, held in Gold Coast, Australia in December 2008.
The 78 revised full papers together with 3 invited talks presented were carefully reviewed and selected from 229 submissions for inclusion in the book. The papers are organized in topical sections on approximation algorithms, online algorithms, data structure and algorithms, game theory, graph algorithms, fixed parameter tractability, distributed algorithms, database, approximation algorithms, computational biology, computational geometry, complexity, networks, optimization as well as routing.
Author(s): Tetsuo Asano (auth.), Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga (eds.)
Series: Lecture Notes in Computer Science 5369 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2008
Language: English
Pages: 948
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Computer Communication Networks; Computer Graphics; Algorithms
Front Matter....Pages -
Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?....Pages 1-1
Some Constrained Notions of Planarity....Pages 2-2
Reachability Problems on Directed Graphs....Pages 3-3
Greedy Construction of 2-Approximation Minimum Manhattan Network....Pages 4-15
The Complexity of Minimum Convex Coloring....Pages 16-27
On the Complexity of Reconfiguration Problems....Pages 28-39
Multiobjective Disk Cover Admits a PTAS....Pages 40-51
Data Stream Algorithms via Expander Graphs....Pages 52-63
Improving the Competitive Ratio of the Online OVSF Code Assignment Problem....Pages 64-76
Optimal Key Tree Structure for Deleting Two or More Leaves....Pages 77-88
Comparing First-Fit and Next-Fit for Online Edge Coloring....Pages 89-99
Selecting Sums in Arrays....Pages 100-111
Succinct and I/O Efficient Data Structures for Traversal in Trees....Pages 112-123
Space-Time Tradeoffs for Longest-Common-Prefix Array Computation....Pages 124-135
Power Domination in $\mathcal{O}^*(1.7548^n)$ Using Reference Search Trees....Pages 136-147
The Isolation Game: A Game of Distances....Pages 148-158
On a Non-cooperative Model for Wavelength Assignment in Multifiber Optical Networks....Pages 159-170
The Complexity of Rationalizing Matchings....Pages 171-182
A Game Theoretic Approach for Efficient Graph Coloring....Pages 183-195
Partitioning a Weighted Tree to Subtrees of Almost Uniform Size....Pages 196-207
An Improved Divide-and-Conquer Algorithm for Finding All Minimum k -Way Cuts....Pages 208-219
On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures....Pages 220-231
An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem....Pages 232-245
The Balanced Edge Cover Problem....Pages 246-257
Firefighting on Trees: (1 − 1/ e )–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm....Pages 258-269
A New Algorithm for Finding Trees with Many Leaves....Pages 270-281
Faster Parameterized Algorithms for Minimum Fill-In ....Pages 282-293
Graph Layout Problems Parameterized by Vertex Cover....Pages 294-305
A Linear Kernel for the k -Disjoint Cycle Problem on Planar Graphs....Pages 306-317
How to Guard a Graph?....Pages 318-329
Tree Decontamination with Temporary Immunity....Pages 330-341
Reconfiguration of Cube-Style Modular Robots Using O (log n ) Parallel Moves....Pages 342-353
Squaring the Circle with Weak Mobile Robots....Pages 354-365
Evaluation of General Set Expressions....Pages 366-377
Computing with Priced Information: When the Value Makes the Price....Pages 378-389
Deductive Inference for the Interiors and Exteriors of Horn Theories....Pages 390-401
Leaf Powers and Their Properties: Using the Trees....Pages 402-413
Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD....Pages 414-423
Minimizing Total Flow-Time: The Unrelated Case....Pages 424-435
Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects....Pages 436-447
Space-Efficient Informational Redundancy....Pages 448-459
Minkowski Sum Selection and Finding....Pages 460-471
Constructing the Simplest Possible Phylogenetic Network from Triplets....Pages 472-483
New Results on Optimizing Rooted Triplets Consistency....Pages 484-495
A Method to Overcome Computer Word Size Limitation in Bit-Parallel Pattern Matching....Pages 496-506
Inducing Polygons of Line Arrangements....Pages 507-519
Free-Form Surface Partition in 3-D....Pages 520-531
Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance....Pages 532-543
Preprocessing Imprecise Points and Splitting Triangulations....Pages 544-555
Efficient Output-Sensitive Construction of Reeb Graphs....Pages 556-567
Signature Theory in Holographic Algorithms....Pages 568-579
The Complexity of SPP Formula Minimization....Pages 580-591
Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol....Pages 592-604
Negation-Limited Inverters of Linear Size....Pages 605-614
3-Message NP Arguments in the BPK Model with Optimal Soundness and Zero-Knowledge....Pages 615-627
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths....Pages 628-643
Detecting Commuting Patterns by Clustering Subtrajectories....Pages 644-655
On the Stretch Factor of Convex Delaunay Graphs....Pages 656-667
Covering a Simple Polygon by Monotone Directions....Pages 668-679
On the Stability of Web Crawling and Web Search....Pages 680-691
Average Update Times for Fully-Dynamic All-Pairs Shortest Paths....Pages 692-703
Computing Frequency Dominators and Related Problems....Pages 704-715
Computing Best Swaps in Optimal Tree Spanners....Pages 716-727
Covering a Point Set by Two Disjoint Rectangles....Pages 728-739
Computing the Maximum Detour of a Plane Graph in Subquadratic Time....Pages 740-751
Finding Long Paths, Cycles and Circuits....Pages 752-763
Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces....Pages 764-775
On Labeled Traveling Salesman Problems....Pages 776-787
Navigating in a Graph by Aid of Its Spanning Tree....Pages 788-799
Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times....Pages 800-811
Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks....Pages 812-823
Bandwidth of Bipartite Permutation Graphs....Pages 824-835
König Deletion Sets and Vertex Covers above the Matching Size....Pages 836-847
Independent Sets of Maximum Weight in Apple-Free Graphs....Pages 848-858
Enumeration of Perfect Sequences of Chordal Graph....Pages 859-870
From Tree-Width to Clique-Width: Excluding a Unit Interval Graph....Pages 871-882
New Results on the Most Significant Bit of Integer Multiplication....Pages 883-894
Sorting with Complete Networks of Stacks....Pages 895-906
Quantum Query Complexity of Boolean Functions with Small On-Sets....Pages 907-918
Unbounded-Error Quantum Query Complexity....Pages 919-930
Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States....Pages 931-942
Back Matter....Pages -
