This book presents the refereed proceedings of the 6th International Symposium on Algorithms and Computation, ISAAC '95, held in Cairns, Australia, in December 1995.
The 45 revised full papers presented together with the abstracts of three invited talks were selected from a total of 130 submissions. The papers address many current aspects of research and advanced applications of algorithms and computations; among the topics covered are graph theory and graph algorithms, computational geometry, computational logics, searching and sorting, approximation and optimization, algebraic manipulation, and coding.
Author(s): Satoru Miyano (auth.), John Staples, Peter Eades, Naoki Katoh, Alistair Moffat (eds.)
Series: Lecture Notes in Computer Science 1004
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1995
Language: English
Pages: 450
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Combinatorics; Probability Theory and Stochastic Processes; Statistics, general; Computer Graphics
Algorithmic problems arising from Genome informatics....Pages 1-1
An approximation algorithm for alphabet indexing problem....Pages 2-11
A fast and space-economical algorithm for length-limited coding....Pages 12-21
Computing in linear time a chord from which a simple polygon is weakly internally visible....Pages 22-31
Competitive searching in polygons—Beyond generalised streets....Pages 32-41
Finding a shortest pair of paths on the plane with obstacles and crossing areas....Pages 42-51
Logspace verifiers, NC, and NP....Pages 52-61
Structure in average case complexity....Pages 62-71
Some geometric lower bounds....Pages 72-81
The I/O-complexity of Ordered Binary-Decision Diagram manipulation....Pages 82-91
Two arc disjoint paths in Eulerian digraphs....Pages 92-101
Finding dense subgraphs....Pages 102-111
Finding smallest supertrees....Pages 112-121
Weighted domination on cocomparability graphs....Pages 122-131
The parallel complexity of approximating the High Degree Subgraph problem....Pages 132-141
Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs....Pages 142-151
Greedy approximations of independent sets in low degree graphs....Pages 152-161
Practical logic....Pages 162-162
An approximation algorithm for MAX 3-SAT....Pages 163-170
Learning of restricted RNLC graph languages....Pages 171-180
Optimal information delivery....Pages 181-187
On the complexity of testing for catastrophic faults....Pages 188-197
Scheduling parallel tasks with individual deadlines....Pages 198-207
Orders of Gauss periods in finite fields....Pages 208-215
A hard problem that is almost always easy....Pages 216-223
Computing the Tutte polynomial of a graph of moderate size....Pages 224-233
More efficient parallel flow algorithms....Pages 234-243
Linear-time in-place selection in less than 3 n comparisons....Pages 244-253
Heap construction: Optimal in both worst and average cases?....Pages 254-263
Fast approximate dictionary matching....Pages 264-273
Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)....Pages 274-283
Searching for a monotone function by independent threshold queries....Pages 284-290
A fast and simple algorithm for identifying 2-monotonic positive Boolean functions....Pages 291-300
Deciding bisimulation and trace equivalences for systems with many identical processes....Pages 301-310
Should Amdahl's Law be repealed?....Pages 311-311
Embeddings of hyper-rings in hypercubes....Pages 312-321
A fast algorithm for computing optimal rectilinear Steiner trees for extremal point sets....Pages 322-331
Algorithms for finding f -colorings of partial k -trees....Pages 332-341
Spanning closed trail and hamiltonian cycle in grid graphs....Pages 342-351
A linear time algorithm for finding maximal planar subgraphs....Pages 352-361
Illumination with orthogonal floodlights....Pages 362-371
No quadrangulation is extremely odd....Pages 372-381
Finding the medial axis of a simple polygon in linear time....Pages 382-391
The first subquadratic algorithm for complete linkage clustering....Pages 392-401
Matching nuts and bolts faster....Pages 402-408
Linear matching-time algorithm for the directed graph isomorphism problem....Pages 409-417
A resource assignment problem on graphs....Pages 418-427
NC algorithms for partitioning sparse graphs into induced forests with an application....Pages 428-437
