default search action
4th ISAAC 1993: Hong Kong
- Kam-Wing Ng, Prabhakar Raghavan, N. V. Balasubramanian, Francis Y. L. Chin:
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
Session 1B
- Martin Fürer
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
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
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 R. 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
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-23 19:17 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: