Algorithms and Computations

Invited Talk.- The Engineering of Some Bipartite Matching Programs.- Session 1(a) - Data Structure I.- General Splay: A Basic Theory and Calculus.- Static Dictionaries Supporting Rank.- Session 1(b) - Parallel & Distributed Computing I.- Multiple Spin-Block Decisions.- Asynchronous Random Polling Dynamic Load Balancing.- Session 2(a) - Approximate Algorithm I.- Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colarability.- Hardness of Approximating Independent Domination in Circle Graphs.- Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs.- Session 2(b) - Computational Intelligence.- Ordered Binary Decision Diagrams as Knowledge-Bases.- Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots.- Session 3(a) - Online Algorithm.- On-Line Load Balancing of Temporary Tasks Revisited.- Online Routing in Triangulations.- Session 3(b) - Complexity Theory I.- The Query Complexity of Program Checking by Constant-Depth Circuits.- Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle.- Session 4(a) - Approximate Algorithm II.- Efficient Approximation Algorithms for Multi-label Map Labeling.- Approximation Algorithms in Batch Processing.- Session 4(b) - Graph Algorithm I.- LexBFS-Ordering in Asteroidal Triple-Free Graphs.- Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs.- Invited Talk.- Approximation Algorithms for Some Clustering and Classification Problems.- Session 5(a) - Computational Geometry I.- How Many People Can Hide in a Terrain?.- Carrying Umbrellas: An Online Relocation Problem on Graphs.- Session 5(b) - Parallel & Distributed Computing II.- Survivable Networks with Bounded Delay: The Edge FailureCase.- Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks.- Session 6(a) - Data Structure II.- Constructing the Suffix Tree of a Tree with a Large Alphabet.- An O(1) Time Algorithm for Generating Multiset Permutations.- Session 6(b) - Complexity Theory II.- Upper Bounds for MaxSat: Further Improved.- A Linear Time Algorithm for Recognizing Regular Boolean Functions.- Session 7(a) - Computational Geometry II.- Station Layouts in the Presence of Location Constraints.- Reverse Center Location Problem.- Session 7(b) - Algorithms in Practice.- Performance Comparison of Linear Sieve and Cubic Sieve Algorithms for Discrete Logarithms over Prime Fields.- External Memory Algorithms for Outerplanar Graphs.- Session 8(a) - Approximate Algorithm III.- A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree.- Approximation Algorithms for Channel Assignment with Constraints.- Session 8(b) - Graph Algorithm II.- Algorithms for Finding Noncrossing Steiner Forests in Plane Graphs.- A Linear Algorithm for Finding Total Colorings of Partial k-Trees.- Invited Talk.- Topology-Oriented Approach to Robust Geometric Computation.- Session 9(a) - Approximate Algorithm IV.- Approximating Multicast Congestion.- Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts.- Session 9(b) - Parallel & Distributed Computing III.- Online Scheduling of Parallel Communications with Individual Deadlines.- A Faster Algorithm for Finding Disjoint Paths in Grids.- Session 10(a) - Computational Geometry III.- Output-Sensitive Algorithms for Uniform Partitions of Points.- Convexifying Monotone Polygons.- Session 10(b) - Graph Algorithm III.- Bisecting Two Subsets in 3-Connected Graphs.- Generalized Maximum Independent Sets for Trees in Subquadratic Time.