Algorithms and Computation: 19th International Symposium, Isaac 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings (Paperback, 2008)

Invited Talk.- Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?.- Some Constrained Notions of Planarity.- Reachability Problems on Directed Graphs.- 1A Approximation Algorithm I.- Greedy Construction of 2-Approximation Minimum Manhattan Network.- The Complexity of Minimum Convex Coloring.- On the Complexity of Reconfiguration Problems.- Multiobjective Disk Cover Admits a PTAS.- 1B Online Algorithm.- Data Stream Algorithms via Expander Graphs.- Improving the Competitive Ratio of the Online OVSF Code Assignment Problem.- Optimal Key Tree Structure for Deleting Two or More Leaves.- Comparing First-Fit and Next-Fit for Online Edge Coloring.- 2A Data Structure and Algorithm.- Selecting Sums in Arrays.- Succinct and I/O Efficient Data Structures for Traversal in Trees.- Space-Time Tradeoffs for Longest-Common-Prefix Array Computation.- Power Domination in Using Reference Search Trees.- 2B Game Theory.- The Isolation Game: A Game of Distances.- On a Non-cooperative Model for Wavelength Assignment in Multifiber Optical Networks.- The Complexity of Rationalizing Matchings.- A Game Theoretic Approach for Efficient Graph Coloring.- 3A Graph Algorithm I.- Partitioning a Weighted Tree to Subtrees of Almost Uniform Size.- An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts.- On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures.- An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem.- The Balanced Edge Cover Problem.- 3B Fixed Parameter Tractability.- Firefighting on Trees: (1???1/e)?Approximation, Fixed Parameter Tractability and a Subexponential Algorithm.- A New Algorithm for Finding Trees with Many Leaves.- Faster Parameterized Algorithms for Minimum Fill-In.- Graph Layout Problems Parameterized by Vertex Cover.- A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs.- 4A Distributed Algorithm.- How to Guard a Graph?.- Tree Decontamination with Temporary Immunity.- Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves.- Squaring the Circle with Weak Mobile Robots.- 4B Database.- Evaluation of General Set Expressions.- Computing with Priced Information: When the Value Makes the Price.- Deductive Inference for the Interiors and Exteriors of Horn Theories.- Leaf Powers and Their Properties: Using the Trees.- 5A Approximation Algorithm II.- Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD.- Minimizing Total Flow-Time: The Unrelated Case.- Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects.- Space-Efficient Informational Redundancy.- 5B Computational Biology.- Minkowski Sum Selection and Finding.- Constructing the Simplest Possible Phylogenetic Network from Triplets.- New Results on Optimizing Rooted Triplets Consistency.- A Method to Overcome Computer Word Size Limitation in Bit-Parallel Pattern Matching.- 6A Computational Geometry I.- Inducing Polygons of Line Arrangements.- Free-Form Surface Partition in 3-D.- Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance.- Preprocessing Imprecise Points and Splitting Triangulations.- Efficient Output-Sensitive Construction of Reeb Graphs.- 6B Complexity I.- Signature Theory in Holographic Algorithms.- The Complexity of SPP Formula Minimization.- Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol.- Negation-Limited Inverters of Linear Size.- 3-Message NP Arguments in the BPK Model with Optimal Soundness and Zero-Knowledge.- 7A Computational Geometry II.- A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths.- Detecting Commuting Patterns by Clustering Subtrajectories.- On the Stretch Factor of Convex Delaunay Graphs.- Covering a Simple Polygon by Monotone Directions.- 7B Network.- On the Stability of Web Crawling and Web Search.- Average Update Times for Fully-Dynamic All-Pairs Shortest Paths.- Computing Frequency Dominators and Related Problems.- Computing Best Swaps in Optimal Tree Spanners.- 8A Optimization.- Covering a Point Set by Two Disjoint Rectangles.- Computing the Maximum Detour of a Plane Graph in Subquadratic Time.- Finding Long Paths, Cycles and Circuits.- Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces.- 8B Routing.- On Labeled Traveling Salesman Problems.- Navigating in a Graph by Aid of Its Spanning Tree.- Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times.- Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks.- 9A Graph Algorithm II.- Bandwidth of Bipartite Permutation Graphs.- Konig Deletion Sets and Vertex Covers above the Matching Size.- Independent Sets of Maximum Weight in Apple-Free Graphs.- Enumeration of Perfect Sequences of Chordal Graph.- From Tree-Width to Clique-Width: Excluding a Unit Interval Graph.- 9B Complexity II.- New Results on the Most Significant Bit of Integer Multiplication.- Sorting with Complete Networks of Stacks.- Quantum Query Complexity of Boolean Functions with Small On-Sets.- Unbounded-Error Quantum Query Complexity.- Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States.