Algorithms and Computation: 5th International Symposium, ISAAC '94 Beijing, P. R. China, August 25–27, 1994 Proceedings

Polynomial equations-solving and its applications....Pages 1-9
Quasi-random combinatorial structures....Pages 10-10
Hamiltonian abstract Voronoi diagrams in linear time....Pages 11-19
Every set of disjoint line segments admits a binary tree....Pages 20-28
The traveling cameraman problem, with applications to automatic optical inspection....Pages 29-37
On determining the congruity of point sets in higher dimensions....Pages 38-46
On random hard sets for NP....Pages 47-55
Computing solutions uniquely collapses the polynomial hierarchy....Pages 56-64
Verifying the determinant in parallel....Pages 65-73
Hardness of approximating graph transformation problem....Pages 74-82
Randomized wait-free naming....Pages 83-91
Unifying themes for network selection....Pages 92-100
Robust asynchronous algorithms in networks with a fault detection ring....Pages 101-109
Distributed algorithms for finding small cycle covers in arbitrary networks....Pages 110-118
A neural network model for quadratic programming with simple upper and lower bounds and its application to linear programming....Pages 119-127
Analysis of the convergency of topology preserving neural networks on learning....Pages 128-136
On helping and interactive proof systems....Pages 137-145
Average time complexity of the SAT 1.2 algorithm....Pages 146-154
Average cost to produce partial orders....Pages 155-163
Two notes on low-density subset sum algorithm....Pages 164-171
Rotation distance, triangulations of planar surfaces and hyperbolic geometry....Pages 172-180
Finitely representable spatial objects and efficient computation....Pages 181-189
Computing all small cuts in undirected networks....Pages 190-198
Edge-coloring and f -coloring for various classes of graphs....Pages 199-207
Edge-disjoint paths in permutation graphs....Pages 208-216
Minimum augmentation to k -edge-connect specified vertices of a graph....Pages 217-225
Algorithmic Chernoff-Hoeffding inequalities in integer programming....Pages 226-233
Approximate pattern matching with samples....Pages 234-242
An efficient optimal algorithm for minimizing the overall communication cost in replicated data management....Pages 243-251
Multispace search: A new optimization approach....Pages 252-260
Realizing degree sequences in parallel....Pages 261-269
Efficient sequential and parallel algorithms for the negative cycle problem....Pages 270-278
Fast and efficient operations on Parallel Priority Queues....Pages 279-287
Heaps with bits....Pages 288-296
Components and projections of curves over finite fields....Pages 297-305
On the approximation of finding various minimal, maximal, and consistent sequences....Pages 306-314
A linear-time algorithm for computing characteristic strings....Pages 315-323
The maximum latency and identification of positive Boolean functions....Pages 324-332
Fast deterministic Hot-Potato routing on processor arrays....Pages 333-341
k -pairwise cluster fault tolerant routing in hypercubes....Pages 342-350
On Steiner minimal trees in grid graphs and its application to VLSI routing....Pages 351-359
Optimal routing of permutations on rings....Pages 360-368
Resource bounded randomness and weakly complete problems....Pages 369-377
Deterministic Ω automata vis-a-vis deterministic Buchi automata....Pages 378-386
Quantum computation and NP-complete problems....Pages 387-395
Separability and one-way functions....Pages 396-404
On the approximation of largest common subtrees and largest common point sets....Pages 405-413
An approximation scheme for some Steiner tree problems in the plane....Pages 414-422
A chain decomposition algorithm for the proof of a property on minimum weight triangulations....Pages 423-427
Generating algorithm for quasi-full Steiner tree....Pages 428-432
Analysing deletions in competitive self-adjusting linear list algorithms....Pages 433-441
Are Fibonacci heaps optimal?....Pages 442-450
Simple and efficient graph compression schemes for dense and complement graphs....Pages 451-459
Improved algorithms for coloring random graphs....Pages 460-468
On the parallel complexity of solving recurrence equations....Pages 469-477
Extended graph connectivity and its gradually increasing parallel complexity....Pages 478-486
Parallel h-v drawings of binary trees....Pages 487-495
An efficient parallel strategy for recognizing series-parallel graphs....Pages 496-504
Orthogonal queries in segments and triangles....Pages 505-513
Further computational geometry in secondary memory....Pages 514-522
Shortest safari routes in simple polygons....Pages 523-530
On greedy tetrahedralization of points in 3D....Pages 532-540
The totally-perfect bipartite graph and its construction....Pages 541-549
k Best Cuts for Circular-Arc graphs....Pages 550-558
Revisiting circular arc graphs....Pages 559-566
Weighted irredundance of interval graphs....Pages 567-574
A reordering operation for an ordered binary decision diagram and an extended framework for combinatorics of graphs....Pages 575-583
On the size of ordered binary decision diagrams representing threshold functions....Pages 584-592
Nonuniform lowness and strong nonuniform lowness....Pages 593-599
Definition and existence of super complexity cores....Pages 600-606
Efficient algorithms for assigning chain-like tasks on a chain-like network computer....Pages 607-615
Manpower scheduling with shift change constraints....Pages 616-624
Fast algorithms for transversal matroid intersection problems....Pages 625-633
A convex hull algorithm on coarse-grained multiprocessor....Pages 634-642
A multiway merging network....Pages 643-651
Reporting and counting intersections of lines within a polygon....Pages 652-659
A new problem in string searching....Pages 660-668
Achieving the shortest clock period by inserting the minimum amount of delay....Pages 669-677
A randomized algorithm to Finite Automata Public Key Cryptosystem....Pages 678-686