Algorithms and Computations : 10th International Symposium, ISAAC'99, Chennai, India, December 16-18, 1999 Proceedings

by ISAAC (Conference); Aggarwal, Alok; Pandu Rangan, C.; Goos, G.; Hartmanis, J.; Leeuwen, J. Van

• ISBN13: 9783540669166
• ISBN10: 3540669167
• Format: Paperback
• Copyright: 2000-01-01
• Publisher: Springer Verlag

Summary

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

Invited Talk
The Engineering of Some Bipartite Matching Programs	p. 1
Data Structure I
General Splay: A Basic Theory and Calculus	p. 4
Static Dictionaries Supporting Rank	p. 18
Parallel & Distributed Computing I
Multiple Spin-Block Decisions	p. 27
Asynchronous Random Polling Dynamic Load Balancing	p. 37
Approximate Algorithm I
Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colarability	p. 49
Hardness of Approximating Independent Domination in Circle Graphs	p. 56
Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs	p. 70
Computational Intelligence
Ordered Binary Decision Diagrams as Knowledge-Bases	p. 83
Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots	p. 93
Online Algorithm
On-Line Load Balancing of Temporary Tasks Revisited	p. 103
Online Routing in Triangulations	p. 113
Complexity Theory I
The Query Complexity of Program Checking by Constant-Depth Circuits	p. 123
Tree-Like Resolution Is Superpolynomially Slower Than DAG-LikeResolution for the Pigeonhole Principle	p. 133
Approximate Algorithm II
Efficient Approximation Algorithms for Multi-label Map Labeling	p. 143
Approximation Algorithms in Batch Processing	p. 153
Graph Algorithm I
LexBFS-Ordering in Asteroidal Triple-Free Graphs	p. 163
Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs	p. 173
Invited Talk
Approximation Algorithms for Some Clustering and Classification Problems	p. 183
Computational Geometry I
How Many People Can Hide in a Terrain?	p. 184
Carrying Umbrellas: An Online Relocation Problem on Graphs	p. 195
Parallel & Distributed Computing II
Survivable Networks with Bounded Delay: The Edge Failure Case	p. 205
Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks	p. 215
Data Structure II
Constructing the Suffix Tree of a Tree with a Large Alphabet	p. 225
An O(1) Time Algorithm for Generating Multiset Permutations	p. 237
Complexity Theory II
Upper Bounds for MaxSat: Further Improved	p. 247
A Linear Time Algorithm for Recognizing Regular Boolean Functions	p. 259
Computational Geometry II
Station Layouts in the Presence of Location Constraints	p. 269
Reverse Center Location Problem	p. 279
Algorithms in Practice
Performance Comparison of Linear Sieve and Cubic Sieve Algorithms forDiscrete Logarithms over Prime Fields	p. 295
External Memory Algorithms for Outerplanar Graphs	p. 307
Approximate Algorithm III
A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree	p. 317
Approximation Algorithms for Channel Assignment with Constraints	p. 327
Graph Algorithm II
Algorithms for Finding Noncrossing Steiner Forests in Plane Graphs	p. 337
A Linear Algorithm for Finding Total Colorings of Partial k-Trees	p. 347
Invited Talk
Topology-Oriented Approach to Robust Geometric Computation	p. 357
Approximate Algorithm IV
Approximating Multicast Congestion	p. 367
Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts	p. 373
Parallel & Distributed Computing III
Online Scheduling of Parallel Communications with Individual Deadlines	p. 383
A Faster Algorithm for Finding Disjoint Paths in Grids	p. 393
Computational Geometry III
Output-Sensitive Algorithms for Uniform Partitions of Points	p. 403
Convexifying Monotone Polygons	p. 415
Graph Algorithm III
Bisecting Two Subsets in 3-Connected Graphs	p. 425
Generalized Maximum Independent Sets for Trees in Subquadratic Time	p. 435
Author Index	p. 447
Table of Contents provided by Publisher. All Rights Reserved.