5. ISAAC 1994: Beijing, China

Session 0

• Wu Wen-Tsün:
  Polynomial Equations-Solving and its Applications. 1-9
  
• Ronald L. Graham:
  Quasi-Random Combinatorial Structures (Abstract). 10
  

Computational Geometry

• Rolf Klein, Andrzej Lingas:
  Hamiltonian Abstract Voronoi Diagrams in Linear Time. 11-19
  
• Prosenjit Bose, Michael E. Houle, Godfried T. Toussaint:
  Every Set of Disjoint Line Segments Admits a Binary Tree. 20-28
  
• Kazuo Iwano, Prabhakar Raghavan, Hisao Tamaki:
  The Traveling Cameraman Problem, with Applications to Automatic Optical Inspection. 29-37
  
• Tatsuya Akutsu:
  On Determining the Congruity of Point Sets in Higher Dimensions. 38-46
  

Computational Complexity

• Ronald V. Book, Osamu Watanabe:
  On Random Hard Sets for NP. 47-55
  
• Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman:
  Computing Solutions Uniquely collapses the Polynomial Hierarchy. 56-64
  
• Miklos Santha, Sovanna Tan:
  Verifying the Determinant in Parallel. 65-73
  
• Chih-Long Lin:
  Hardness of Approximating Graph Transformation Problem. 74-82
  

Distributed Algorithms

• Alessandro Panconesi, Marina Papatriantafilou, Philippas Tsigas, Paul M. B. Vitányi:
  Randomized Wait-Free Naming. 83-91
  
• Sanguthevar Rajasekaran, Wang Chen, Shibu Yooseph:
  Unifying Themes for Network Selection. 92-100
  
• Moshe Molcho, Shmuel Zaks:
  Robust Asynchronous Algorithms in Networks with a Fault Detection Ring. 101-109
  
• Esther Jennings, Lenka Motyckova:
  Distributed Algorithms for Finding Small Cycle Covers in Arbitrary Networks. 110-118
  

Learning

• Xiang-Sun Zhang, Hui-Can Zhu:
  A Neural Network Model for Quadratic Programming with Simple Upper and Lower Bounds and its Application to Linear Programming. 119-127
  
• Daming Zhu, Shaohan Ma, Hongze Qiu:
  Analysis of the Convergency of Topology Preserving Neural Networks on Learning. 128-136
  
• Vikraman Arvind, Johannes Köbler, Rainer Schuler:
  On Helping and Interactive Proof Systems. 137-145
  
• Jun Gu, Qian-Ping Gu:
  Average Time Complexity of the SAT 1.2 Algorithm. 146-154
  

Combinatorial Algorithms

• Jingsen Chen:
  Average Cost to Produce Partial Orders. 155-163
  
• Daxing Li, Shaohan Ma:
  Two Notes on Low-Density Subset Sum Algorithms. 164-171
  
• Jin-yi Cai, Michael D. Hirsch:
  Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry. 172-180
  
• Yongmao Chen, Terence R. Smith:
  Finitely Representables Spatial Objects and Efficient Computation. 181-189
  

Graph Algorithms

• Hiroshi Nagamochi, Kazuhiro Nishimura, Toshihide Ibaraki:
  Computing All Small Cuts in Undirected Networks. 190-198
  
• Xiao Zhou, Takao Nishizeki:
  Edge-Coloring and f-Coloring for Various Classes of Graphs. 199-207
  
• C. P. Gopalakrishnan, C. Pandu Rangan:
  Edge-Disjoint Paths in Permutation Graphs. 208-216
  
• Satoshi Taoka, Toshimasa Watanabe:
  Minimum Augmentation to k-Edge-Connect Specified Vertices of a Graph. 217-225
  

Randomized Algorithms

• Anand Srivastav, Peter Stangier:
  Algorthmic Chernoff-Hoeffding Inequalitiers in Integer Programming. 226-233
  
• Tadao Takaoka:
  Approximate Pattern Matching with Samples. 234-242
  
• Xuemin Lin, Maria E. Orlowska:
  An Efficient Optimal Algorithm for Minimizing the Overall Communication Cost in Replicated Data Management. 243-251
  
• Jun Gu:
  Multispace Search: A New Optimization Approach. 252-260
  

Parallel Algorithms

• Srinivasa Rao Arikati, Anil Maheshwari:
  Realizing Degree Sequences in Parallel. 261-269
  
• Dimitris J. Kavvadias, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis:
  Efficient Sequential and Parallel Algorithms for the Negative Cycle Problem. 270-278
  
• Danny Z. Chen, Xiaobo Hu:
  Fast and Efficient Operations on Parallel Priority Queues. 279-287
  
• Svante Carlsson, Jingsen Chen, Christer Mattsson:
  Heaps with Bits. 288-296
  

Algebraic Algorithms

• Joachim von zur Gathen, Igor Shparlinski:
  Components and Projections of Curves over Finite Fields. 297-305
  
• Martin Middendorf:
  On the Approximation of Finding Various Minimal, Maximal, and Consistent Sequences. 306-314
  
• Michio Nakanishi, Morio Hasidume, Minoru Ito, Akihiro Hashimoto:
  A Linear-Time Algorithm for Computing Characteristic Strings. 315-323
  
• Kazuhisa Makino, Toshihide Ibaraki:
  The Maximum Latency and Identification of Positive Boolean Functions. 324-332
  

VISI and Routing

• Michael Kaufmann, Harald Lauer, Heiko Schröder:
  Fast Deterministic Hot-Potato Routing on Processor Arrays. 333-341
  
• Qian-Ping Gu, Shietung Peng:
  k-Pairwise Cluster Fault Tolerant Routing in Hypercubes. 342-350
  
• Michael Kaufmann, Shaodi Gao, Krishnaiyan Thulasiraman:
  On Steiner Minimal Trees in Grid Graphs and Its Application to VLSI Routing. 351-359
  
• Xiaojun Shen, Qing Hu, Hao Dai, Xiangzu Wang:
  Optimal Routing of Permutations on Rings. 360-368
  

Computational Complexity

• Klaus Ambos-Spies, Sebastiaan Terwijn, Xizhong Zheng:
  Resource Bounded Randomness and Weakly Complete Problems. 369-377
  
• Sriram C. Krishnan, Anuj Puri, Robert K. Brayton:
  Deterministic w Automata vis-a-vis Deterministic Buchi Automata. 378-386
  
• Takashi Mihara, Tetsuro Nishino:
  Quantum Computation and NP-Complete Problems. 387-395
  
• Lance Fortnow, John D. Rogers:
  Separability and One-Way Functions. 396-404
  

Approximation and Optimization

• Tatsuya Akutsu, Magnús M. Halldórsson:
  On the Approximation of Largest Common Subtrees and Largest Common Point Sets. 405-413
  
• Tao Jiang, Lusheng Wang:
  An Approximation Scheme for Some Steiner Tree Problems in the Plane. 414-422
  
• Bo-Ting Yang, Yin-Feng Xu, Zhao-yong You:
  A Chain Decomposition Algorithm for the Proof of a Property on Minimum Weight Triangulations. 423-427
  
• Jiyu Ding:
  The Generating Algorithm for Quasi-Full Steiner Trees. 428-432
  

Data Structures

• Lucas Chi Kwong Hui, Charles U. Martel:
  Analysing Deletions in Competitive Self-Adjusting Linear List. 433-441
  
• Diab Abuaiadh, Jeffrey H. Kingston:
  Are Fibonacci Heaps Optimal? 442-450
  
• Ming-Yang Kao, Shang-Hua Teng:
  Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs. 451-459
  
• C. R. Subramanian:
  Improved Algorithms for Coloring Random Graphs. 460-468
  

Parallel Algorithms

• Oscar H. Ibarra, Nicholas Q. Trân:
  On the Parallel Complexity of Solving Recurrence Equations. 469-477
  
• Chuzo Iwamoto, Kazuo Iwama:
  Extended Graph Connectivity and Its Gradually Increasing Parallel Complexity. 478-486
  
• Panagiotis Takis Metaxas, Grammati E. Pantziou, Antonios Symvonis:
  Parallel h-v Drawings of Binary Trees. 487-495
  
• Sun-Yuan Hsieh, Chin-Wen Ho:
  An Efficient Parallel Strategy for Recognizing Series-Parallel Graphs. 496-504
  

Geometric Algorithms

• Takeshi Tokuyama:
  Orthogonal Queries in Segments and Triangles. 505-513
  
• Binhai Zhu:
  Further Computational Geometry in Secondary Memory. 514-522
  
• Xuehou Tan, Tomio Hirata:
  Shortest Safari Routes in Simple Polygon. 523-531
  
• Francis Y. L. Chin, Cao An Wang:
  On Greedy Tetrahedralization of Points in 3D. 532-540
  

Graph Algorithms

• Kunihiro Fujiyoshi, Yoji Kajitani, Hiroshi Niitsu:
  The Totally-Perfect Bipartite Graph and Its Construction. 541-549
  
• Kuo-Hui Tsai, D. T. Lee:
  k-Best Cuts for Circular-Arc Graphs. 550-558
  
• Lin Chen:
  Revisiting Circular Arc Graphs. 559-566
  
• C. Pandu Rangan, Maw-Shang Chang:
  Weighted Irredundance of Interval Graphs. 567-574
  

Complexity

• Seiichiro Tani, Hiroshi Imai:
  A Reordering Operation for an Ordered Binary Decision Diagram and an Extended Framework for Combinatorics of Graphs. 575-583
  
• Kazuhisa Hosaka, Yasuhiko Takenaga, Shuzo Yajima:
  On the Size of Ordered Binary Decision Diagrams Representing Threshold Functions. 584-592
  
• Hong-Zhou Li, Guan-Ying Li:
  Nonuniform Lowness and Strong Nonuniform Lowness. 593-599
  
• Ingrid Biehl:
  Definition and Existence of Super Complexity Cores. 600-606
  

Combinatorial Algorithms

• Gilbert H. Young, Chi-lok Chan:
  Efficient Algorithms for Assigning Chain-Like Tasks on a Chain-Like Network Computer. 607-615
  
• Hoong Chuin Lau:
  Manpower Scheduling with Shift Change Constraints. 616-624
  
• Ying Xu, Harold N. Gabow:
  Fast Algorithms for Transversal Matroid Intersection Problems. 625-633
  
• Xiaotie Deng:
  A Convex Hull Algorithm on Coarse-Grained Multiprocessors. 634-64
  

Combinatorial Algorithms

• De-Lei Lee, Kenneth E. Batcher:
  A Multiway Merging Network. 643-651
  
• Tetsuo Asano:
  Reporting and Counting Intersections of Lines within a Polygon. 652-659
  
• George Havas, Jin Xian Lian:
  A New Problem in String Searching. 660-668
  

Distributed and Rondomized Algorithms

• Shangzhi Sun, David Hung-Chang Du, Guoliang Xue:
  Achieving the Shortest Clock Period by Inserting the Minimum Amount of Delay. 669-677
  
• Feng Bao, Yoshihide Igarashi:
  A Randomized Algorithm to Finite Automata Public Key Cryptosystem. 678-686