Algorithms and Computation: Third International Symposium, ISAAC'92 Nagoya, Japan, December 16–18, 1992 Proceedings

Methods in parallel algorithmics and who may need to know them?....Pages 1-4
Rectilinear paths among rectilinear obstacles....Pages 5-20
Linear time algorithms for k-cutwidth problem....Pages 21-30
The k-edge-connectivity augmentation problem of weighted graphs....Pages 31-40
Principal lattice of partitions of submodular functions on graphs: Fast algorithms for principal partition and generic rigidity....Pages 41-50
The application of the searching over separators strategy to solve some NP-complete problems on planar graphs....Pages 51-60
Parallel and on-line graph coloring algorithms....Pages 61-70
Competitive analysis of the Round Robin algorithm....Pages 71-77
Competitive analysis of the on-line algorithms for multiple stacks systems....Pages 78-87
Self-adjusting augmented search trees....Pages 88-96
Algorithms for a class of Min-Cut and Max-Cut problem....Pages 97-105
Algorithms for rectilinear optimal multicast tree problem....Pages 106-115
Approximating treewidth and pathwidth of some classes of perfect graphs....Pages 116-125
Graph spanners and connectivity....Pages 126-134
Randomized range-maxima in nearly-constant parallel time....Pages 135-144
Fault-tolerant broadcasting in binary jumping networks....Pages 145-154
Routing problems on the mesh of buses....Pages 155-164
Selection networks with 8 n log 2 n size and O (log n ) depth....Pages 165-174
Relativizations of the P=? NP and other problems: Some developments in structural complexity theory....Pages 175-186
Boolean circuit complexity....Pages 187-187
Searching a solid pseudo 3-sided orthoconvex grid....Pages 188-197
An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects....Pages 198-208
Topologically consistent algorithms related to convex polyhedra....Pages 209-218
Characterizing and recognizing visibility graphs of Funnel-shaped polygons....Pages 219-228
On the complexity of composite numbers....Pages 229-238
On malign input distributions for algorithms....Pages 239-248
Lowness and the complexity of sparse and tally descriptions....Pages 249-258
Honest iteration schemes of randomizing algorithms....Pages 259-268
Approximating vertices of a convex polygon with grid points in the polygon....Pages 269-278
Algorithms for determining the geometrical congruity in two and three dimensions....Pages 279-288
On the relationships among constrained geometric structures....Pages 289-298
Generating small convergent systems can be extremely hard....Pages 299-308
Chew\'s theorem revisited — uniquely normalizing property of nonlinear term rewriting systems....Pages 309-318
Higher order communicating processes with Value-Passing, Assignment and return of results....Pages 319-331
Searching informed game trees....Pages 332-341
How to generate realistic sample problems for network optimization....Pages 342-350
Generalized assignment problems....Pages 351-369
Recognizing an envelope of lines in linear time....Pages 370-377
Approximation of polygonal curves with minimum number of line segments....Pages 378-387
Wiring knock-knee layouts: A global approach....Pages 388-399
Algorithms for finding non-crossing paths with minimum total length in plane graphs....Pages 400-409
On symmetry of information and polynomial time invertibility....Pages 410-419
On probabilistic ACC circuits with an exact-threshold output gate....Pages 420-429
Computational and statistical indistinguishabilities....Pages 430-438
On symmetric differences of NP-hard sets with weakly-P-selective sets....Pages 439-448
Restricted track assignment with applications....Pages 449-458
A simple test for the consecutive ones property....Pages 459-468
The longest common subsequence problem for small alphabet size between many strings....Pages 469-478
The implicit dictionary problem revisited....Pages 479-488
Sorting in-place with a worst case complexity of n log n −1.3 n+O (log n ) comparisons and ε n log n+O (1) transports....Pages 489-498
Sorting and/by merging finger trees....Pages 499-508