7. ISAAC 1996: Osaka, Japan

Tetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano, Subhash Suri (Eds.): Algorithms and Computation, 7th International Symposium, ISAAC '96, Osaka, Japan, December 16-18, 1996, Proceedings. Lecture Notes in Computer Science 1178 Springer 1996, ISBN 3-540-62048-6

Session 1: Invited Presentation

Mikhail J. Atallah, Danny Z. Chen:
Applications of a Numbering Scheme for Polygonal Obstacles in the Plane. 1-24

Jonathan S. Turner: Multicast Communication in High Speed Networks.

David Bremner:
Incremental Convex Hull Algorithms Are Not Output Sensitive. 26-35
Alon Efrat, Otfried Schwarzkopf:
Separating and Shattering Long Line Segments. 36-44
Olivier Devillers, Matthew J. Katz:
Optimal Line Bipartitions of Point Sets. 45-54
Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama:
Interval Finding and Its Application to Data Mining. 55-64

David Fernández-Baca, Jens Lagergren:
On the Approximability of the Steiner Tree Problem in Phylogeny. 65-74
Magnús M. Halldórsson, Keisuke Tanaka:
Approximation and Special Cases of Common Subtrees and Editing Distance. 75-84
Ying Choi, Tak Wah Lam:
Two-Dimensional Dynamic Dictionary Matching. 85-94
Alvis Brazma, Esko Ukkonen, Jaak Vilo:
Discovering Unbounded Unions of Regular Pattern Languages from Positive Examples (Extended Abstract). 95-104

Tamal K. Dey, János Pach:
Extremal Problems for Geometric Hypergraphs. 105-114
Alon Efrat, Matthew J. Katz:
Computing Fair and Bottleneck Matchings in Geormetric Graphs. 115-125
Mark de Berg, Olivier Devillers, Marc J. van Kreveld, Otfried Schwarzkopf, Monique Teillaud:
Computing the Maximum Overlap of Two Convex Polygons Under Translations. 126-135

Kazuyoshi Hayase, Hiroshi Imai:
OBDDs of a Monotone Function and of Its Prime Implicants. 136-145
Maw-Shang Chang:
Algorithms for Maximum Matching and Minimum Fill-in on Chordal Bipartite Graphs. 146-155
Sheng-Lung Peng, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu, Chuan Yi Tang:
Graph Searching on Chordal Graphs. 156-165

Takeaki Uno:
An Algorithm for Enumerating all Directed Spanning Trees in a Directed Graph. 166-173
Ton Kloks, Haiko Müller, C. K. Wong:
Vertex Ranking of Asteroidal Triple-Free Graphs. 174-182

Rolf Niedermeier:
Recursively Divisible Problems. 183-192
Eric Allender, Klaus-Jörn Lange:
StUSPACE(log n) <= DSPACE(log²n / log log n). 193-202

Xiao Zhou, Syurei Tamura, Takao Nishizeki:
Finding Edge-Disjoint Paths in Partial k-Trees (Extended Abstract). 203-212
Tsan-sheng Hsu, Ming-Yang Kao:
Optimal Augmentation for Bipartite Componentwise Biconnectiviy in Linear Time (Extended Abstract). 213-222
Ka Wong Chong, Tak Wah Lam:
Towards More Precise Parallel Biconnectivity Approximation. 223-232

Andris Ambainis:
The Complexity of Probabilistic versus Deterministic Finite Automata. 233-238
Bruce E. Litow:
Bounded Length UCFG Equivalence. 239-246

D. T. Lee, C. F. Shen:
The Steiner Minimal Tree Problem in the lambda-Geormetry Plane. 247-255
Siu-Wing Cheng, Naoki Katoh, Manabu Sugai:
A Study of the LMT-Skeleton. 256-265
Cao An Wang, Francis Y. L. Chin, Yin-Feng Xu:
A New Subgraph of Minimum Weight Triangulations. 266-274

Grammati E. Pantziou, Alan Roberts, Antonios Symvonis:
Dynamic Tree Routing under the ``Matching with Consumption'' Model. 275-284
Michael E. Houle, Gavin Turner:
Dimension-Exchange Token Distribution on the Mesh and the Torus. 285-294
Jae-Ha Lee, Chan-Su Shin, Kyung-Yong Chwa:
Directed Hamiltonian Packing in d-Dimensional Meshes and Its Application (Extended Abstract). 295-304

Evanthia Papadopoulou:
k-Pairs Non-Crossing Shortest Paths in a Simple Polygon. 305-314
Andrzej Lingas, V. Soltan:
Minimum Convex Partition of a Polygon with Holes by Cuts in Given Directions. 315-325

Tatsuya Hayashi, Koji Nakano, Stephan Olariu:
Efficient List Ranking on the Reconfigurable Mesh, with Applications. 326-335
Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff:
Periodic Merging Networks. 336-345
Gordon T. Wilfong:
Minimum Wavelength in an All-Optical Ring Network. 346-355

Tzuoo-Hawn Yeh, Cheng-Ming Kuo, Chin-Laung Lei, Hsu-Chun Yen:
Competitive Analysis of On-Line Disk Scheduling. 356-365
Jacques Verriet:
Scheduling Interval Ordered Tasks with Non-Uniform Deadlines. 366-375

Kouichi Sakurai, Yuliang Zheng:
Cryptographic Weaknesses in the Round Transformation Used in a Block Cipher with Provable Immunity Against Linear Cryptanalysis (Extended Abstract). 376-385
Tsuyoshi Takagi, Shozo Naito:
The Multi-variable Modular Polynomial and Its Applications to Cryptography. 386-396

Tsan-sheng Hsu, Dian Rae Lopez:
Bounds and Algorithms for a Practical Task Allocation Model (Extended Abstract). 397-406
Panagiota Fatourou, Paul G. Spirakis:
Scheduling Algorithms for Strict Multithreaded Computations. 407-416
Esteban Feuerstein, Alejandro Strejilevich de Loma:
On Multi-threaded Paging. 417-426

Boris Ryabko, Andrei Fionov:
A Fast and Efficient Homophonic Coding Algorithm. 427-435
Osamu Watanabe, Osamu Yamashita:
An Improvement of the Digital Cash Protocol of Okamoto and Ohta. 436-445