Algorithms and Computation: 8th International Symposium, ISAAC ’97 Singapore, December 17–19, 1997 Proceedings

Toshihide Ibaraki (auth.), Hon Wai Leong, Hiroshi Imai, Sanjay Jain (eds.)3540638903, 9783540638902

This book constitutes the refereed proceedings of the 8th International Symposium on Algorithms and Computation, ISAAC’97, held in Singapore in December 1997. The 42 revised full papers presented were selected from a total of 98 submissions. The scope of the volume spans the whole area of algorithms from discrete mathematics and complexity theory to algorithms design and evaluation in a variety of applicational areas. Among the topics addressed are scheduling and logistics, networking and routing, combinatorial optimization, graph-computations, algorithmic learning, computational geometry, etc.

---

Table of contents :
Solving NP-hard combinatorial problems in the practical sense Invited presentation….Pages 1-1
Airline crew-scheduling problem with many irregular flights….Pages 2-11
Practical approach to a facility location problem for large-scale logistics….Pages 12-21
Hard instance generation for SAT….Pages 22-31
Playing tetris on meshes and multi-dimensional Shearsort ….Pages 32-41
Formulation of the addition-shift-sequence problem and its complexity….Pages 42-51
Weighted and unweighted selection algorithms for k sorted sequences….Pages 52-61
An adaptive distributed fault-tolerant routing algorithm for the star graph….Pages 62-71
Multi-color routing in the undirected hypercube….Pages 72-81
Competitive source routing on tori and meshes….Pages 82-91
Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs….Pages 92-101
Augmenting edge and vertex connectivities simultaneously….Pages 102-111
Two-face horn extensions….Pages 112-121
Decremental maintenance of reachability in hypergraphs and minimum models of horn formulae….Pages 122-131
Algorithmic analysis of multithreaded algorithms….Pages 132-132
A characterization of planar graphs by pseudo-line arrangements….Pages 133-142
Optimal fault-tolerant broadcasting in trees….Pages 143-152
A theoretical framework of hybrid approaches to MAX SAT….Pages 153-162
Exponential lower bounds on the size of OBDDs representing integer division….Pages 163-172
On-line versus off-line in money-making strategies with brokerage….Pages 173-182
Decision-making by hierarchies of discordant agents….Pages 183-192
A new efficient off-line anonymous cash scheme….Pages 193-201
Approximating unweighted connectivity problems in parallel….Pages 202-211
A randomized linear work EREW PRAM algorithm to find a minimum spanning forest….Pages 212-222
Efficient parallel algorithms for planar st-graphs….Pages 223-232
Peg-solitaire, string rewriting systems and finite automata….Pages 233-242
On the size of probabilistic formulae….Pages 243-252
Homophonic coding with logarithmic memory size….Pages 253-262
Complexity and modeling aspects of mesh refinement into quadrilaterals….Pages 263-272
Topology oriented vs. exact arithmetic — Experience in implementing the three-dimensional convex hull algorithm….Pages 273-282
The complexity of learning branches and strategies from queries….Pages 283-292
Singularities make spatial join scheduling hard….Pages 293-302
A faster one-dimensional topological compaction algorithm….Pages 303-313
Algorithms for finding optimal disjoint paths around a rectangle….Pages 314-323
An algorithm for finding a region with the minimum total L 1 from prescribed terminals….Pages 324-333
On defect sets in bipartite graphs (extended abstract)….Pages 334-343
Dynamic programming on distance-hereditary graphs….Pages 344-353
On the equivalence in complexity among basic problems on bipartite and parity graphs….Pages 354-363
All-cavity maximum matchings….Pages 364-373
Fast algorithms for computing β -Skeletons and their relatives….Pages 374-383
A branch-and-cut approach for minimum weight triangulation….Pages 384-393
An efficient approximation scheme for the subset-sum problem….Pages 394-403
Competitive call control in mobile networks….Pages 404-413
Generalized swap-with-parent schemes for self-organizing sequential linear lists….Pages 414-423