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 BibTeX

@proceedings{DBLP:conf/isaac/1996,
  editor    = {Tetsuo Asano and
               Yoshihide Igarashi and
               Hiroshi Nagamochi and
               Satoru Miyano and
               Subhash Suri},
  title     = {Algorithms and Computation, 7th International Symposium, ISAAC
               '96, Osaka, Japan, December 16-18, 1996, Proceedings},
  booktitle = {ISAAC},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1178},
  year      = {1996},
  isbn      = {3-540-62048-6},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Session 1: Invited Presentation

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

Session 2: Invited Presentation

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

Session 3a

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

Session 3b

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

Session 4a

Tamal K. Dey, János Pach: Extremal Problems for Geometric Hypergraphs. 105-114 BibTeX
Alon Efrat, Matthew J. Katz: Computing Fair and Bottleneck Matchings in Geormetric Graphs. 115-125 BibTeX
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 BibTeX

Session 4b

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

Session 5a

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

Session 5b

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

Session 6a

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

Session 6b

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

Session 7a

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

Session 7b

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

Session 8a

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

Session 8b

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

Session 8a

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

Session 9b

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 BibTeX
Tsuyoshi Takagi, Shozo Naito: The Multi-variable Modular Polynomial and Its Applications to Cryptography. 386-396 BibTeX

Session 10a

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

Session 10b

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