This book constitutes the refereed proceedings of the 7th International Symposium on Algorithms and Computation, ISAAC'96, held in Osaka, Japan, in December 1996.
The 43 revised full papers were selected from a total of 119 submissions; also included are an abstract of one invited talk and a full version of a second. Among the topics covered are computational geometry, graph theory, graph algorithms, combinatorial optimization, searching and sorting, networking, scheduling, and coding and cryptology.
Author(s): Mikhail J. Atallah, Danny Z. Chen (auth.), Tetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano, Subhash Suri (eds.)
Series: Lecture Notes in Computer Science 1178
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1996
Language: English
Pages: 458
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Computer Communication Networks; Computer Graphics; Computational Mathematics and Numerical Analysis
Applications of a numbering scheme for polygonal obstacles in the plane....Pages 1-24
Multicast communication in high speed networks....Pages 25-25
Incremental convex hull algorithms are not output sensitive....Pages 26-35
Separating and shattering long line segments....Pages 36-44
Optimal line bipartitions of point sets....Pages 45-54
Interval finding and its application to data mining....Pages 55-64
On the approximability of the Steiner tree problem in phylogeny....Pages 65-74
Approximation and special cases of common subtrees and editing distance....Pages 75-84
Two-dimensional dynamic dictionary matching....Pages 85-94
Discovering unbounded unions of regular pattern languages from positive examples....Pages 95-104
Extremal problems for geometric hypergraphs....Pages 105-114
Computing fair and bottleneck matchings in geometric graphs....Pages 115-125
Computing the maximum overlap of two convex polygons under translations....Pages 126-135
OBDDs of a monotone function and of its prime implicants....Pages 136-145
Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs....Pages 146-155
Graph searching on chordal graphs....Pages 156-165
An algorithm for enumerating all directed spanning trees in a directed graph....Pages 166-173
Vertex ranking of asteroidal triple-free graphs....Pages 174-182
Recursively divisible problems....Pages 183-192
StUSPACE(log n) ⊂-DSPACE(log 2 n/log log n)....Pages 193-202
Finding edge-disjoint paths in partial k -trees....Pages 203-212
Optimal augmentation for bipartite componentwise biconnectivity in linear time....Pages 213-222
Towards more precise parallel biconnectivity approximation....Pages 223-232
The complexity of probabilistic versus deterministic finite automata....Pages 233-238
Bounded length UCFG equivalence....Pages 239-246
The Steiner Minimal Tree problem in the λ-geometry plane....Pages 247-255
A study of the LMT-skeleton....Pages 256-265
A new subgraph of minimum weight triangulations....Pages 266-274
Dynamic tree routing under the “matching with consumption” model....Pages 275-284
Dimension-exchange token distribution on the mesh and the torus....Pages 285-294
Directed hamiltonian packing in d -dimensional meshes and its application....Pages 295-304
k -pairs non-crossing shortest paths in a simple polygon....Pages 305-314
Minimum convex partition of a polygon with holes by cuts in given directions....Pages 315-325
Efficient list ranking on the reconfigurable mesh, with applications....Pages 326-335
Periodic merging networks....Pages 336-345
Minimizing wavelengths in an all-optical ring network....Pages 346-355
Competitive analysis of on-line disk scheduling....Pages 356-365
Scheduling interval ordered tasks with non-uniform deadlines....Pages 366-375
Cryptographic weaknesses in the round transformation used in a block cipher with provable immunity against linear cryptanalysis....Pages 376-385
The multi-variable modular polynomial and its applications to cryptography....Pages 386-396
Bounds and algorithms for a practical task allocation model (extended abstract)....Pages 397-406
Scheduling algorithms for strict multithreaded computations....Pages 407-416
On multi-threaded Paging....Pages 417-426
A fast and efficient homophonic coding algorithm....Pages 427-435
An improvement of the digital cash protocol of Okamoto and Ohta....Pages 436-445
