Algorithms and Computation: 10th International Symposium, ISAAC’99 Chennai, India, December 16–18, 1999 Proceedings

The Engineering of Some Bipartite Matching Programs....Pages 1-3
General Splay: A Basic Theory and Calculus....Pages 4-17
Static Dictionaries Supporting Rank....Pages 18-26
Multiple Spin-Block Decisions....Pages 27-36
Asynchronous Random Polling Dynamic Load Balancing....Pages 37-48
Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colarability ....Pages 49-55
Hardness of Approximating Independent Domination in Circle Graphs....Pages 56-69
Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs....Pages 70-82
Ordered Binary Decision Diagrams as Knowledge-Bases....Pages 83-92
Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots....Pages 93-102
On-Line Load Balancing of Temporary Tasks Revisited....Pages 103-112
Online Routing in Triangulations....Pages 113-122
The Query Complexity of Program Checking by Constant-Depth Circuits....Pages 123-132
Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle....Pages 133-142
Efficient Approximation Algorithms for Multi-label Map Labeling....Pages 143-152
Approximation Algorithms in Batch Processing....Pages 153-162
LexBFS-Ordering in Asteroidal Triple-Free Graphs....Pages 163-172
Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs....Pages 173-182
Approximation Algorithms for Some Clustering and Classification Problems....Pages 183-183
How Many People Can Hide in a Terrain?....Pages 184-194
Carrying Umbrellas: An Online Relocation Problem on Graphs....Pages 195-204
Survivable Networks with Bounded Delay: The Edge Failure Case....Pages 205-214
Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks....Pages 215-224
Constructing the Suffix Tree of a Tree with a Large Alphabet....Pages 225-236
An O (1) Time Algorithm for Generating Multiset Permutations....Pages 237-246
Upper Bounds for MaxSat: Further Improved....Pages 247-258
A Linear Time Algorithm for Recognizing Regular Boolean Functions....Pages 259-268
Station Layouts in the Presence of Location Constraints....Pages 269-278
Reverse Center Location Problem....Pages 279-294
Performance Comparison of Linear Sieve and Cubic Sieve Algorithms for Discrete Logarithms over Prime Fields....Pages 295-306
External Memory Algorithms for Outerplanar Graphs....Pages 307-316
A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree....Pages 317-326
Approximation Algorithms for Channel Assignment with Constraints....Pages 327-336
Algorithms for Finding Noncrossing Steiner Forests in Plane Graphs....Pages 337-346
A Linear Algorithm for Finding Total Colorings of Partial k-Trees ....Pages 347-356
Topology-Oriented Approach to Robust Geometric Computation....Pages 357-366
Approximating Multicast Congestion....Pages 367-372
Approximating the Minimum k -way Cut in a Graph via Minimum 3-way Cuts....Pages 373-382
Online Scheduling of Parallel Communications with Individual Deadlines....Pages 383-392
A Faster Algorithm for Finding Disjoint Paths in Grids....Pages 393-402
Output-Sensitive Algorithms for Uniform Partitions of Points....Pages 403-414
Convexifying Monotone Polygons....Pages 415-424
Bisecting Two Subsets in 3-Connected Graphs....Pages 425-434
Generalized Maximum Independent Sets for Trees in Subquadratic Time....Pages 435-445