xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx ISAAC '96 xxxxxxxxxxxxxx xxxxxxx xxxxxxxxxxxxxx xxxxxxx the 7th International Symposium on xxxxxxxxxxxxxx xxxxxxx Algorithms and Computation xxxxxxxxxxxxxx xxxxxxx December 16-18, 1996 xxxxxxxxxxxxxx xxxxxxx Senri Life Science Center xxxxxxxxxxxxxx xxxxxxx Osaka, Japan xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx --------------------------------------------------------------------- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% SUNDAY, December 15, 1996 %%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% RECEPTION: 6:00 pm -- 8:00 pm Life Science Center, 9F %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% MONDAY, December 16, 1996 %%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Session 1: 9:30 -- 10:30 chair: Subhash Suri Applications of a Numbering Scheme for Polygonal Obstacles in the Plane by Mikhail Atallah (Purdue University) .........Break: 10:30 -- 10:45 am............ Session 2: 10:45 -- 11:45 chair: Satoru Miyano Multicast Communication in High Speed Networks. by Jonathan Turner (Washington University) .......Group Photo: 11:45 am -- noon......... .........Lunch: noon -- 13:30 pm............. Session 3a -- chair M. Atallah Computational Geometry (1) 13:30 Incremental convex hull algorithms are not output sensitive. ----- David Bremner 14:00 Separating and Shattering Long Line Segments. ----- Alon Efrat and Otfried Schwarzkopf 14:30 Optimal Line Bipartitions of Point Sets. ----- Olivier Devillers and Matthew J. Katz 15:00 Interval Finding and Its Application to Data Mining. ----- Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita and Takeshi Tokuyama Session 3b -- chair T. Akutsu Genome Science & Combinatorial Pattern Matching 13:30 On the Approximability of the Steiner Tree Problem in Phylogeny. ----- David Fern{\' a}ndez-Baca and Jens Lagergren 14:00 Approximation and Special Cases of Common Subtrees and Editing Distance. ----- Magn\'us M. Halld\'orsson and Keisuke Tanaka 14:30 Two-Dimensional Dynamic Dictionary Matching. ----- Ying Choi and Tak Wah Lam 15:00 Discovering Unbounded Unions of Pattern Languages from Positive Examples. ----- Alvis Br\=azma, Esko Ukkonen and Jaak Vilo .........Break: 15:30 -- 16:00 pm................ Session 4a -- chair M. Sharir Computational Geometry (2) 16:00 Extremal Problems for Geometric Hypergraphs. ----- Tamal K. Dey and J\'anos Pach 16:30 Computing Fair and Bottleneck Matchings in Geometric Graphs. ----- Alon Efrat and Matthew J. Katz 17:00 Computing the Maximum Overlap of Two Convex Polygons Under Translations. ----- Mark de Berg, Olivier Devillers, Marc van Kreveld, Otfried Schwarzkopf and Monique Teillaud Session 4b -- chair T. Hirata Graph Algorithms (1) 16:00 OBDDs of a Monotone Function and of Its Prime Implicants. ----- Kazuyoshi Hayase and Hiroshi Imai 16:30 Algorithms for Maximum Matching and Minimum Fill-in on Chordal Bipartite Graphs. ----- Maw-Shang Chang 17:00 Graph Searching on Chordal Graphs. ----- S. L. Peng, M. T. Ko, C. W. Ho, T. S. Hsu and C. Y. Tang %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% TUESDAY, December 17, 1996 %%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Session 5a -- chair M. Golin Graph Algorithms (2) 9:00 An Algorithm for Enumerating all Directed Spanning Trees in a Directed Graph. ----- Takeaki Uno 9:30 Vertex ranking of asteroidal triple-free graphs. ----- T. Kloks, H. M{\"u}ller and C. K. Wong Session 5b -- chair S. Miyano Complexity Theory (1) 9:00 Recursively Divisible Problems. ----- Rolf Niedermeier 9:30 StUSPACE($\log n$) in DSPACE($\log^2 n/\log\log n$). ----- Eric Allender and Klaus-J\"orn Lange .........Break: 10:00 -- 10:30 am............... Session 6a -- chair M. Golin Graph Algorithms (3) 10:30 Finding Edge-Disjoint Paths in Partial {\it k}-Trees. ----- Xiao Zhou, Syurei Tamura and Takao Nishizeki 11:00 Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time. ----- Tsan-sheng Hsu and Ming-Yang Kao 11:30 Towards More Precise Parallel Biconnectivity Approximation. ----- Ka Wong Chong and Tak Wah Lam Session 6b -- chair S. Miyano Complexity Theory (2) 10:30 The Complexity of Probabilistic versus Deterministic Finite Automata. ----- Andris Ambainis 11:00 Bounded Length Unambiguous Context-Free Grammar Equivalence. ----- B. Litow ........Lunch: noon -- 13:30 pm................... Session 7a -- chair D.-Z. Du Computational Geometry (3) 13:30 The Steiner Minimal Tree Problem in the ${\lambda}$-geometry Plane. ----- D.T. Lee and C.F. Shen 14:00 A Study of the {\it LMT}-skeleton. ----- Siu-Wing Cheng, Naoki Katoh and Manabu Sugai 14:30 A New Subgraph of Minimum Weight Triangulations. ----- Cao An Wang, Francis Chin and Yin-Feng Xu Session 7b -- chair Y. Igarashi Parallel & Distributed Algorithms (1) 13:30 Dynamic Tree Routing under the ``Matching with Consumption'' Model. ----- Grammati E. Pantziou, Alan Roberts and Antonis Symvonis 14:00 Dimension-Exchange Token Distribution on the Mesh and the Torus. ----- Michael E. Houle and Gavin Turner 14:30 Directed hamiltonian packing in d-dimensional meshes and its application. ----- Jae-Ha Lee, Chan-Su Shin and Kyung-Yong Chwa ..........Break: 15:30 -- 16:00 pm.................... Session 8a -- chair S. Suri Computational Geometry (4) 16:00 k-Pairs non-crossing shortest paths in a simple polygon. ----- Evanthia Papadopoulou 16:30 Minimum Convex Partition of a Polygon with Holes by Cuts in Given Directions. ----- A. Lingas and V. Soltan Session 8b -- chair J. Turner Parallel & Distributed Algorithms (1) 16:00 Efficient List Ranking on the Reconfigurable Mesh, with Applications. ----- Tatsuya Hayashi, Koji Nakano and Stephan Olariu 16:30 Periodic merging networks. ----- Miros{\l}aw Kuty{\l}owski, Krzysztof Lory\'s and Brigitte Oesterdiekhoff 17:00 Minimizing Wavelengths in an All-Optical Ring Network. ----- Gordon Wilfong %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% WEDNESDAY, December 18, 1996 %%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Session 9a -- chair V. Chandru Scheduling and On-line Algorithms (1) 9:00 Competitive Analysis of On-line Disk Scheduling. ----- Tzuoo-Hawn Yeh, Cheng-Ming Kuo, Chin-Laung Lei, and Hsu-Chun Yen 9:30 Scheduling interval ordered tasks with non-uniform deadlines. ----- Jacques Verriet Session 9b -- chair M. Ogihara Cryptography (1) 9:00 Cryptographic Weaknesses in the Round Transformation Used in a Block Cipher with Provable Immunity Against Linear Cryptanalysis. ----- Kouichi Sakurai and Yuliang Zheng 9:30 The multi-variable modular polynomial and its applications to cryptography. ----- Tsuyoshi Takagi and Shozo Naito .........Break: 10:00 -- 10:30 am...................... Session 10a -- chair V. Chandru Scheduling and On-line Algorithms (2) 10:30 Bounds and Algorithms for a Practical Task Allocation Model. ----- Tsan-sheng Hsu and Dian Rae Lopez 11:00 Scheduling Algorithms for Strict Multithreaded Computations. ----- Panagiota Fatourou and Paul Spirakis 11:30 On Multi-threaded Paging. ----- Esteban Feuerstein and Alejandro Strejilevich de Loma Session 10b -- chair M. Ogihara Cryptography (2) 10:30 A Fast and Efficient Homophonic Coding Algorithm. ----- Boris Ryabko and Andrey Fionov 11:00 An Improvement of the Digital Cash Protocol of Okamoto and Ohta. ----- Osamu Watanabe and Osamu Yamashita 12:00 End of program