4. ISAAC 1993: Hong Kong

@proceedings{DBLP:conf/isaac/1993,
  editor    = {Kam-Wing Ng and
               Prabhakar Raghavan and
               N. V. Balasubramanian and
               Francis Y. L. Chin},
  title     = {Algorithms and Computation, 4th International Symposium, ISAAC
               '93, Hong Kong, December 15-17, 1993, Proceedings},
  booktitle = {ISAAC},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {762},
  year      = {1993},
  isbn      = {3-540-57568-5},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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 BibTeX
• Gautam Das, Paul J. Heffernan: Constructing Degree-3 Spanners with Other Sparseness Properties. 11-20 BibTeX
• Katrin Dobrindt, Mariette Yvinec: Remembering Conflicts in History Yields Dynamic Algorithms. 21-30 BibTeX

Session 1B

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

Session 2A

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

Session 2B

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

Session 3A

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

Session 3B

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

Session 4A

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

Session 4B

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

Session 5

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

Session 6A

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

Session 6B

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

Session 7

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

Session 8A

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

Session 8B

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

Session 9

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

Session 10A

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

Session 10B

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

Session 11A

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

Session 11B

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

Session 12A

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

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 BibTeX
• Siu-Wing Cheng, Andrew Lim, Ching-Ting Wu: Optimal Rectilinear Steiner Tree for Extremal Point Sets. 523-532 BibTeX
• Ulrich Fößmeier, Michael Kaufmann, Alexander Zelikovsky: Faster Approximation Algorithms for the Rectilinear Steiner Tree Problem. 533-542 BibTeX