Mikhail J. Atallah, Danny Z. Chen (auth.), Tetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano, Subhash Suri (eds.)3540620486, 9783540620488
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.
Table of contents :
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
Reviews
There are no reviews yet.