• 
  Kam-Wing Ng, Prabhakar Raghavan, N. V. Balasubramanian, Francis Y. L. Chin (Eds.): Algorithms and Computation, 4th International Symposium, ISAAC '93, Hong Kong, December 15-17, 1993, Proceedings. Springer 1993 Lecture Notes in Computer Science ISBN 3-540-57568-5

Session 1A

• 
  Mark de Berg, Mark H. Overmars, Leonidas J. Guibas, Otfried Schwarzkopf, Monique Teillaud, Dan Halperin, Micha Sharir: Reaching a Goal with Directional Uncertainty. 1-10
• 
  Gautam Das, Paul J. Heffernan: Constructing Degree-3 Spanners with Other Sparseness Properties. 11-20
• 
  Katrin Dobrindt, Mariette Yvinec: Remembering Conflicts in History Yields Dynamic Algorithms. 21-30

Session 1B

• 
  Martin Fürer, C. R. Subramanian, C. E. Veni Madhavan: Coloring Random Graphs in Polynomial Expected Time. 31-37
• 
  Takao Asano: Graphical Degree Sequence Problems with Connectivity Requirements. 38-47
• 
  Yang Dai, Hiroshi Imai, Kazuo Iwano, Naoki Katoh: How to Treat Delete Requests in Semi-Online Problems. 48-57

Session 2A

• 
  Svante Carlsson, Håkan Jonsson, Bengt J. Nilsson: Finding the Shortest Watchman Route in a Simple Polygon. 58-67
• 
  Xuehou Tan, Tomio Hirata: Constructing Shortest Watchman Routes by Divide-and-Conquer. 68-77
• 
  Frank Hoffmann, Klaus Kriegel: A Graph Coloring Result and Its Consequences for Some Guarding Problems. 78-87

Session 2B

• 
  Anders Dessmark, Klaus Jansen, Andrzej Lingas: The Maximum k-Dependent and f-Dependent Set Problem. 88-98
• 
  Jun-ya Takahashi, Hitoshi Suzuki, Takao Nishizeki: Finding Shortest Non-Crossing Rectilinear Paths in Plane Regions. 98-107
• 
  Ton Kloks: Treewidth of Circle Graphs. 108-117

Session 3A

• 
  Jingsen Chen: A Framework for Constructing Heap-Like Structures In-Place. 118-127
• 
  C. M. Khoong, H. W. Leong: Double-Ended Binomial Queues. 128-137
• 
  Rudolf Fleischer: A Simple Balanced Search Tree with O(1) Worst-Case Update Time. 138-146

Session 3B

• 
  Sabine R. Öhring, Sajal K. Das: Mapping Dynamic Data and Algorithm Structures into Product Networks. 147-156
• 
  J. C. Cogolludo, Sanguthevar Rajasekaran: Permutation Routing on Reconfigurable Meshes. 157-166
• 
  Miltos D. Grammatikakis, D. Frank Hsu, Frank K. Hwang: Adaptive and Oblivious Algorithms for D-Cube Permutation Routing. 167-175

Session 4A

• 
  Anand Srivastav, Peter Stangier: On Quadratic Lattice Approximations. 176-184
• 
  Toshihiro Fujito: A 2or3-Approximation of the Matroid Matching Problem. 185-190

Session 4B

• 
  Simant Dube: Using Fractal Geometry for Solving Divide-and-Conquer Recurrences. 191-200
• 
  Frank Ruskey: Simple Combinatorial Gray Codes Constructed by Reversing Sublists. 201-208

Session 5

• 
  Allan Borodin: Time Space Tradeoffs (Getting Closer to the Barrier?). 209-220

Session 6A

• 
  Hing Leung: Separating Exponentially Ambiguous NFA from Polynomially Ambiguous NFA. 221-229
• 
  Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf: Threshold Computation and Cryptographic Security. 230-239
• 
  Rolf Niedermeier, Peter Rossmanith: On the Power of Reading and Writing Simultaneously in Parallel Computation. 240-249
• 
  Ronald V. Book: Relativizing Complexity Classes With Random Oracles. 250-258

Session 6B

• 
  Arthur L. Liestman, Dana S. Richards: An Introduction to Perpetual Gossiping. 259-266
• 
  Takahiro Ikeda: A Probabilistic Selection Network with Butterfly Networks. 267-276
• 
  Satoshi Fujita, Masafumi Yamashita, Tadashi Ae: Optimal Group Gossiping in Hypercubes Under Wormhole Routing Model. 277-286
• 
  Sara Bitan, Shmuel Zaks: Optimal Linear Broadcast Routing with Capacity Limitations. 287-296

Session 7

• 
  Baruch Awerbuch, Frank Thomson Leighton: Multicommodity Flows: A Survey of Recent Research. 297-302

Session 8A

• 
  Xin He, Ming-Yang Kao: Parallel Construction of Canonical Ordering and Convex Drawing of Triconnected Planar Graphs. 303-312
• 
  Tetsuo Asano, Naoki Katoh: Number Theory Helps Line Detection in Digital Images. 313-322
• 
  Danny Z. Chen: Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon. 323-332

Session 8B

• 
  Karsten Weihe: Multicommodity Flows in Even, Planar Networks. 333-342
• 
  Heike Ripphausen-Lipa, Dorothea Wagner, Karsten Weihe: Linear Time Algorithms for Disjoint Two-Face Paths Problems in Planar Graphs. 343-352
• 
  Xiaotie Deng, Andy Mirzaian: Robot Mapping: Foot-Prints versus Tokens. 353-362

Session 9

• 
  Mihalis Yannakakis: Recent Developments on the Approximability of Combinatorial Problems. 363-368

Session 10A

• 
  Tatsuaki Okamoto: On the Relationship among Cryptographic Physical Assumptions. 369-378
• 
  Christoph Meinel, Stephan Waack: Separating Complexity Classes Related to Bounded Alternating omega-Branching Programs. 379-388
• 
  Seiichiro Tani, Kiyoharu Hamaguchi, Shuzo Yajima: The Complexity of the Optimal Variable Ordering Problems of Shared Binary Decision Diagrams. 389-398
• 
  Dimitris J. Kavvadias, Christos H. Papadimitriou, Martha Sideri: On Horn Envelopes and Hypergraph Transversals. 399-405

Session 10B

• 
  Marek Chrobak, Lawrence L. Larmore, Nick Reingold, Jeffery Westbrook: Page Migration Algorithms Using Work Functions. 406-415
• 
  Esteban Feuerstein, Alberto Marchetti-Spaccamela: Memory Paging for Connectivity and Path Problems in Graphs. 416-425
• 
  Lucas Chi Kwong Hui, Charles U. Martel: Randomized Competitive Algorithms for Successful and Unsuccessful Search on Self-adjusting Linear Lists. 426-435
• 
  Hisashi Koga: Randomized On-line Algorithms for the Page Replication Problem. 436-445

Session 11A

• 
  Susanne E. Hambrusch, Hung-Yi Tu: New Algorithms for Minimizing the Longest Wire Length during Circuit Compaction. 446-455
• 
  Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih: Parallel Algorithms for Single-Layer Channel Routing. 456-465

Session 11B

• 
  Alok Aggarwal, Takeshi Tokuyama: Consecutive Interval Query and Dynamic Programming on Intervals. 466-475
• 
  Alok Aggarwal, Takeshi Tokuyama: An Improved Algorithm for the Traveler's Problem. 476-485

Session 12A

• 
  Yoshiyuki Karuno, Hiroshi Nagamochi, Toshihide Ibaraki: Vehicle Scheduling on a Tree with Release and Handling Times. 486-495
• 
  Chi-lok Chan, Gilbert H. Young: Scheduling Algorithms for a Chain-like Task System. 496-505
• 
  Gerard J. Chang, C. Pandu Rangan, Satyan R. Coorg: Weighted Independent Perfect Domination on Cocomparability Graphs. 506-514

Session 12B

• 
  D. P. Wang, N. F. Huang, H. S. Chao, Richard C. T. Lee: Plane Sweep Algorithms for the Polygonal Approximation Problems with Applications. 515-522
• 
  Siu-Wing Cheng, Andrew Lim, Ching-Ting Wu: Optimal Rectilinear Steiner Tree for Extremal Point Sets. 523-532
• 
  Ulrich Fößmeier, Michael Kaufmann, Alexander Zelikovsky: Faster Approximation Algorithms for the Rectilinear Steiner Tree Problem. 533-542