Algorithms and computation. 5th international symposium, ISAAC '94, Beijing, P. R. China, August 25-27, 1994. Proceedings (Q1331631)

The articles of this volume will be reviewed individually. The 4th symposium (1993) has been reviewed (see Zbl 0856.00042 and Zbl 0851.00081). Indexed articles: \textit{Wu, Wen-tsun}, Polynomial equations-solving and its applications, 1-9 [Zbl 0953.01500] \textit{Klein, Rolf; Lingas, Andrzej}, Hamiltonian abstract Voronoi diagrams in linear time, 11-19 [Zbl 0953.68604] \textit{Bose, Prosenjit; Houle, Michael E.; Toussaint, Godfried}, Every set of disjoint line segments admits a binary tree, 20-28 [Zbl 0953.68602] \textit{Iwano, Kazuo; Raghavan, Prabhakar; Tamaki, Hisao}, The traveling cameraman problem, with applications to automatic optical inspection, 29-37 [Zbl 0953.68614] \textit{Akutsu, Tatsuya}, On determining the congruity of point sets in higher dimensions, 38-46 [Zbl 0953.68606] \textit{Book, Ronald V.; Watanabe, Osamu}, On random hard sets for NP, 47-55 [Zbl 0953.68544] \textit{Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.}, Computing solutions uniquely collapses the polynomial hierarchy, 56-64 [Zbl 0953.68541] \textit{Santha, Miklos; Tan, Sovanna}, Verifying the determinant in parallel, 65-73 [Zbl 0953.68559] \textit{Lin, Chih-Long}, Hardness of approximating graph transformation problem, 74-82 [Zbl 0953.68542] \textit{Panconesi, Alessandro; Papatriantafilou, Marina; Tsigas, Philippas; Vitányi, Paul}, Randomized wait-free naming, 83-91 [Zbl 0953.68573] \textit{Jennings, Esther; Motyčková, Lenka}, Distributed algorithms for finding small cycle covers in arbitrary networks, 110-118 [Zbl 0953.68641] \textit{Zhang, Xiang-sun; Zhu, Hui-can}, A neural network model for quadratic programming with simple upper and lower bounds and its application to linear programming, 119-127 [Zbl 0953.90562] \textit{Zhu, Daming; Ma, Shaohan; Qiu, Hongze}, Analysis of the convergency of topology preserving neural networks on learning, 128-136 [Zbl 0953.68588] \textit{Arvind, V.; Köbler, J.; Schuler, R.}, On helping and interactive proof systems, 137-145 [Zbl 0953.68554] \textit{Gu, Jun; Gu, Qian-Ping}, Average time complexity of the SAT1. 2 algorithm, 146-154 [Zbl 0953.68552] \textit{Chen, Jingsen}, Average cost to produce partial orders, 155-163 [Zbl 0953.68528] \textit{Li, Daxing; Ma, Shaohan}, Two notes on low-density subset sum algorithms, 164-171 [Zbl 0953.68558] \textit{Cai, Jin-Yi; Hirsch, Michael D.}, Rotation distance, triangulations of planar surfaces and hyperbolic geometry, 172-180 [Zbl 0953.68611] \textit{Chen, Yongmao; Smith, Terence R.}, Finitely representable spatial objects and efficient computation, 181-189 [Zbl 0953.68530] \textit{Nagamochi, Hiroshi; Nishimura, Kazuhiro; Ibaraki, Toshihide}, Computing all small cuts in undirected networks, 190-198 [Zbl 0953.68578] \textit{Zhou, Xiao; Nishizeki, Takao}, Edge-coloring and \(f\)-coloring for various classes of graphs, 199-207 [Zbl 0953.05500] \textit{Gopalakrishnan, C. P.; Rangan, C. Pandu}, Edge-disjoint paths in permutation graphs, 208-216 [Zbl 0953.05502] \textit{Taoka, Satoshi; Watanabe, Toshimasa}, Minimum augmentation to \(k\)-edge-connect specified vertices of a graph, 217-225 [Zbl 0953.05503] \textit{Srivastav, Anand; Stangier, Peter}, Algorithmic Chernoff-Hoeffding inequalities in integer programming, 226-233 [Zbl 0953.90559] \textit{Takaoka, Tadao}, Approximate pattern matching with samples, 234-242 [Zbl 0953.68551] \textit{Lin, Xuemin; Orlowska, Maria E.}, An efficient optimal algorithm for minimizing the overall communication cost in replicated data management, 243-251 [Zbl 0953.68531] \textit{Gu, Jun}, Multispace search: A new optimization approach, 252-260 [Zbl 0953.68596] \textit{Arikati, Srinivasa; Maheshwari, Anil}, Realizing degree sequences in parallel, 261-269 [Zbl 0953.05509] \textit{Kavvadias, Dimitris; Pantziou, Grammati E.; Spirakis, Paul G.; Zaroliagis, Christos D.}, Efficient sequential and parallel algorithms for the negative cycle problem, 270-278 [Zbl 0953.05507] \textit{Chen, Danny Z.; Hu, Xiaobo}, Fast and efficient operations on parallel priority queues, 279-287 [Zbl 0953.68522] \textit{Carlsson, Svante; Chen, Jingsen; Mattsson, Christer}, Heaps with bits, 288-296 [Zbl 0953.68524] \textit{von zur Gathen, Joachim; Shparlinski, Igor}, Components and projections of curves over finite fields, 297-305 [Zbl 0953.14501] \textit{Middendorf, Martin}, On the approximation of finding various minimal, maximal, and consistent sequences, 306-314 [Zbl 0953.68635] \textit{Nakanishi, Michio; Hasidume, Morio; Ito, Minoru; Hashimoto, Akihiro}, A linear-time algorithm for computing characteristic strings, 315-323 [Zbl 0953.68632] \textit{Makino, Kazuhisa; Ibaraki, Toshihide}, The maximum latency and identification of positive Boolean functions, 324-332 [Zbl 0953.94503] \textit{Kaufmann, Michael; Lauer, Harald; Schröder, Heiko}, Fast deterministic hot-potato routing on processor arrays, 333-341 [Zbl 0953.68507] \textit{Gu, Qian-Ping; Peng, Shietung}, \(k\)-pairwise cluster fault tolerant routing in hypercubes, 342-350 [Zbl 0953.68500] \textit{Kaufmann, Michael; Gao, Shaodi; Thulasiraman, K.}, On Steiner minimal trees in grid graphs and its application to VLSI routing, 351-359 [Zbl 0953.68579] \textit{Shen, Xiaojun; Hu, Qing; Dai, Hao; Wang, Xiangzu}, Optimal routing of permutations on rings, 360-368 [Zbl 0953.68508] \textit{Ambos-Spies, Klaus; Terwijn, Sebastiaan A.; Zheng, Xizhong}, Resource bounded randomness and weakly complete problems, 369-377 [Zbl 0953.68546] \textit{Krishnan, Sriram C.; Puri, Anuj; Brayton, Robert K.}, Deterministic \(\omega\) automata vis-a-vis deterministic Büchi automata, 378-386 [Zbl 0953.68563] \textit{Mihara, Takashi; Nishino, Tetsuro}, Quantum computation and NP-complete problems, 387-395 [Zbl 0953.68545] \textit{Fortnow, Lance; Rogers, John}, Separability and one-way functions, 396-404 [Zbl 0953.68547] \textit{Akutsu, Tatsuya; Halldórsson, Magnús M.}, On the approximation of largest common subtrees and largest common point sets, 405-413 [Zbl 0953.68555] \textit{Jiang, Tao; Wang, Lusheng}, An approximation scheme for some Steiner tree problems in the plane, 414-422 [Zbl 0953.68576] \textit{Yang, Bo-Ting; Xu, Yin-Feng; You, Zhao-Yong}, A chain decomposition algorithm for the proof of a property on minimum weight triangulations, 423-427 [Zbl 0953.68613] \textit{Ding, Jiyu}, The generating algorithm for quasi-full Steiner trees, 428-432 [Zbl 0953.68584] \textit{Hui, Lucas Chi Kwong; Martel, Charles U.}, Analysing deletions in competitive self-adjusting linear list algorithms, 433-441 [Zbl 0953.68633] \textit{Abuaiadh, Diab; Kingston, Jeffrey H.}, Are Fibonacci heaps optimal?, 442-450 [Zbl 0953.68521] \textit{Kao, Ming-Yang; Teng, Shang-Hua}, Simple and efficient graph compression schemes for dense and complement graphs, 451-459 [Zbl 0953.68583] \textit{Subramanian, C. R.}, Improved algorithms for coloring random graphs, 460-468 [Zbl 0953.05508] \textit{Ibarra, Oscar H.; Trân, Nicholas Q.}, On the parallel complexity of solving recurrence equations, 469-477 [Zbl 0953.68639] \textit{Iwamoto, Chuzo; Iwama, Kazuo}, Extended graph connectivity and its gradually increasing parallel complexity, 478-486 [Zbl 0953.68553] \textit{Metaxas, Panagiotis T.; Pantziou, Grammati E.; Symvonis, Antonis}, Parallel h-v drawings of binary trees, 487-495 [Zbl 0953.68609] \textit{Hsieh, Sun-Yuan; Ho, Chin-Wen}, An efficient parallel strategy for recognizing series-parallel graphs, 496-504 [Zbl 0953.68577] \textit{Tokuyama, Takeshi}, Orthogonal queries in segments and triangles, 505-513 [Zbl 0953.68525] \textit{Zhu, Binhai}, Further computational geometry in secondary memory, 514-522 [Zbl 0953.68603] \textit{Tan, Xuehou; Hirata, Tomio}, Shortest safari routes in simple polygons, 523-531 [Zbl 0953.68612] \textit{Chin, Francis Y.; Wang, Cao An}, On greedy tetrahedralization of points in 3D, 532-540 [Zbl 0953.68607] \textit{Fujiyoshi, Kunihiro; Kajitani, Yoji; Niitsu, Hiroshi}, The totally-perfect bipartite graph and its construction, 541-549 [Zbl 0953.68585] \textit{Tsai, K. H.; Lee, D. T.}, \(k\) best cuts for circular-arc graphs, 550-558 [Zbl 0953.68605] \textit{Chen, Lin}, Revisiting circular arc graphs, 559-566 [Zbl 0953.68582] \textit{Pandu Rangan, C.; Chang, Maw-Shang}, Weighted irredundance of interval graphs, 567-574 [Zbl 0953.05511] \textit{Tani, Seiichiro; Imai, Hiroshi}, A reordering operation for an ordered binary decision diagram and an extended framework for combinatorics of graphs, 575-583 [Zbl 0953.68586] \textit{Hosaka, Kazuhisa; Takenaga, Yasuhiko; Yajima, Shuzo}, On the size of ordered binary decision diagrams representing threshold functions, 584-592 [Zbl 0953.68580] \textit{Li, Hong-Zhou; Li, Guan-Ying}, Nonuniform lowness and strong nonuniform lowness, 593-599 [Zbl 0953.68543] \textit{Biehl, Ingrid}, Definition and existence of super complexity cores, 600-606 [Zbl 0953.68562] \textit{Young, Gilbert H.; Chan, Chi-Lok}, Efficient algorithms for assigning chain-like tasks on a chain-like network computer, 607-615 [Zbl 0953.68511] \textit{Lau, Hoong Chuin}, Manpower scheduling with shift change constraints, 616-624 [Zbl 0953.90516] \textit{Xu, Ying; Gabow, Harold N.}, Fast algorithms for transversal matroid intersection problems, 625-633 [Zbl 0953.68634] \textit{Deng, Xiaotie}, A convex hull algorithm on coarse-grained multiprocessors, 634-642 [Zbl 0953.68601] \textit{Lee, De-Lei; Batcher, Kenneth E.}, A multiway merging network, 643-651 [Zbl 0953.68526] \textit{Asano, Tetsuo}, Reporting and counting intersections of lines within a polygon, 652-659 [Zbl 0953.68610] \textit{Havas, George; Lian, Jin Xian}, A new problem in string searching, 660-668 [Zbl 0953.68527] \textit{Sun, Shangzhi; Du, David H. C.; Xue, Guoliang}, Achieving the shortest clock period by inserting the minimum amount of delay, 669-677 [Zbl 0953.94502] \textit{Bao, Feng; Igarashi, Yoshihide}, A randomized algorithm to finite automata public key cryptosystem, 678-686 [Zbl 0953.94500]