4. ISAAC 1993: Hong Kong

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. Lecture Notes in Computer Science 762 Springer 1993, 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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