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

Alok Aggarwal, C. Pandu Rangan (auth.)3540669167, 9783540669166

This book constitutes the refereed proceedings of the 10th International Symposium on Algorithms and Computation, ISAAC’99, held in Chennai, India, in December 1999.
The 40 revised full papers presented together with four invited contributions were carefully reviewed and selected from 71 submissions. Among the topics covered are data structures, parallel and distributed computing, approximation algorithms, computational intelligence, online algorithms, complexity theory, graph algorithms, computational geometry, and algorithms in practice.

---

Table of contents :
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