SIGAL International Symposium on Algorithms 1990: Tokyo, Japan

Session I-1: Invited Talk

• Zvi Galil:
  Recent Progress in String Algorithms. 1
  

Session I-2: Invited Talk

• Nicholas Pippenger:
  Selection Networks. 2-11
  

Session A-1

• Hiroshi Nagamochi, Toshihide Ibaraki:
  Computing Edge-Connectivity in Multiple and Capacitated Graphs. 12-20
  
• Hiroshi Imai, Kazuo Iwano:
  Efficient Sequential and Parallel Algorithms for Planar Minimum Cost Flow. 21-30
  

Session B-1

• Osamu Watanabe, Seinosuke Toda:
  Structural Analyses on the Complexity of Inverting Functions. 31-38
  
• Eric Allender:
  Oracles versus Proof Techniques that Do Not Relativize. 39-52
  

Session A-2

• Maw-Shang Chang, Chuan Yi Tang, Richard C. T. Lee:
  20-Relative Neighborhood Graphs Are Hamiltonian. 53-65
  
• Tung-Hsin Su, Ruei-Chuan Chang:
  The K-Gabriel Graphs and Their Applications. 66-75
  

Session B-2

• Borivoje Djokic, Masahiro Miyakawa, Satoshi Sekiguchi, Ichiro Semba, Ivan Stojmenovic:
  Parallel Algorithms for Generating Subsets and Set Partitions. 76-85
  
• Yijie Han:
  Parallel Algorithms for Linked List and Beyond. 86-100
  

Session A-3

• Pavol Hell, Jørgen Bang-Jensen, Jing Huang:
  Local Tournaments and Proper Circular Arc Gaphs. 101-108
  
• Kuo-Hui Tsai, Wen-Lian Hsu:
  Fast Algorithms for the Dominating Set Problem on Permutation Graphs. 109-117
  

Session B-3

• Wenceslas Fernandez de la Vega, Sampath Kannan, Miklos Santha:
  Two Probabilistic Results on Merging. 118-127
  
• Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal:
  Randomized Broadcast in Networks. 128-137
  

Session I-3: Invited Talk

• Rolf Klein, Kurt Mehlhorn, Stefan Meiser:
  On the Construction of Abstract Voronoi Diagrams, II. 138-154
  

Session I-4: Invited Talk

• Bernard Chazelle:
  Searching in Higher Dimension. 155
  

Session A-4

• David G. Kirkpatrick, Feng Gao:
  Finding Extrema with Unary Predicates. 156-164
  
• David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri:
  Implicitly Searching Convolutions and Computing Depth of Collision. 165-180
  

Session B-4

• Toshiya Itoh:
  Characterization for a Family of Infinitely Many Irreducible Equally Spaced Polynominals. 181-190
  
• Michel Cosnard, Jean-Laurent Philippe:
  Distributed Algorithms for Deciphering. 191-200
  

Session A-5

• Kazuo Iwano, Susan Yeh:
  An Efficient Algorithm for Optimal Loop Parallelization. 201-210
  
• Wim Pijls, Arie de Bruin:
  Another View on the SSS^* Algorithm. 211-220
  

Session B-5

• Lane A. Hemachandra:
  Algorithms from Complexity Theory: Polynominal-Time Operations for Complex Sets. 221-231
  
• Uwe Schöning:
  Complexity Cores and Hard Problem Instances. 232-240
  

Session A-6

• Xuehou Tan, Tomio Hirata, Yasuyoshi Inagaki:
  Spatial Point Location and Its Applications. 241-250
  
• Svante Carlsson, Christos Levcopoulos, Ola Petersson:
  Sublinear Merging and Natural Merge Sort. 251-260
  
• Leonidas J. Guibas, David Salesin, Jorge Stolfi:
  Constructing Strongly Convex Approximate Hulls with Inaccurate Primitives. 261-270
  

Session B-6

• Kazuo Murota:
  Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation. 271-280
  
• Maria M. Klawe, Frank Thomson Leighton:
  A Tight Lower Bound on the Size of Planar Permutation Networks. 281-287
  

Session I-5: Invited Talk

• Refael Hassin:
  Simultaneous Solution of Families of Problems. 288-299
  

Session A-7

• Tetsuo Asano, Takeshi Tokuyama:
  Algorithms for Projecting Points to Give the Most Uniform Distribution with Applications to Hashing. 300-309
  
• Efthymios Anagnostou, Vassilios G. Polimenis, Leonidas J. Guibas:
  Topological Sweeping in Three Dimensions. 310-317
  

Session B-7

• Kwong-fai Chan, Tak Wah Lam:
  Finding Least-Weight Subsequences with Fewer Processors. 318-327
  
• Yijie Han, Yoshihide Igarashi:
  Derandomization by Exploiting Redundancy and Mutual Independence. 328-337
  

Session A-8

• Hillel Gazit, Gary L. Miller:
  Planar Separators and the Euclidean Norm. 338-347
  
• David Avis:
  On the Complexity of Isometric Embedding in the Hypercube. 348-357
  

Session B-8

• Nicola Santoro, Peter Widmayer:
  Distributed Function Evaluation in the Presence of Transmission Faults. 358-367
  
• Sara Bitan, Shmuel Zaks:
  Optimal Linear Broadcast. 368-377
  

Session A-9

• Toshimasa Watanabe, Yasuhiko Higashi, Akira Nakamura:
  Graph Augmentation Problems for a Specified Set of Vertices. 378-387
  
• Qingzhou Wang, Kam-Hoi Cheng:
  A Heuristic Algorithm for the k-Center Problem with Vertex Weight. 388-396
  

Session B-9

• Hussein M. Alnuweiri, Viktor K. Prasanna:
  Parallel Convexity Algorithms for Digitized Images on a Linear Array of Processors. 397-406
  
• Wen-Jing Hsu, Xiaola Lin:
  Parallel Algorithms for Labeling Image Components. 407-418
  

Session A-10

• Herbert Edelsbrunner, Micha Sharir:
  A Hyperplane Incidence Problem with Applications to Counting Distances. 419-428
  
• Kazumiti Numata, Takeshi Tokuyama:
  Splitting a Configuration in a Simplex. 429-438
  
• János Pach, Richard Pollack, Emo Welzl:
  Weaving Patterns of Lines and Segments in Space. 439-446
  

Session B-10

• Andrzej Lingas:
  Efficient Parallel Algorithms for Path Problems in Planar Directed Graphs. 447-457
  
• Hitoshi Suzuki, Chiseko Yamanaka, Takao Nishizeki:
  Parallel Algorithms for Finding Steiner Forests in Planar Graphs. 458-467
  
• Vassilis J. Tsotras, B. Gopinath, George W. Hart:
  Optimally Managing the History of an Evolving Forest. 468-478