Computing and Combinatorics

1. Front Matter

   Pages I-XII

   PDF

2. Invited Presentations

   1. Algorithmic Approaches to Information Retrieval and Data Mining

      • Christos H. Papadimitriou

      Pages 1-1

   2. Combinatorial Problems Arising in Massive Data Sets

      • Fan Chung Graham

      Pages 2-2

   3. Estimating Parameters of Monotone Boolean Functions

      • Michael J. Fischer

      Pages 3-3

   4. De-amortization of Algorithms

      • S. Rao Kosaraju, Mihai Pop

      Pages 4-14

3. Computational Geometry

   1. On Computing New Classes of Optimal Triangulations with Angular Constraints

      • Yang Dai, Naoki Katoh

      Pages 15-24

   2. Maximum Weight Triangulation and Its Application on Graph Drawing

      • Cao An Wang, Francis Y. Chin, Bo Ting Yang

      Pages 25-34

   3. The Colored Sector Search Tree: A Dynamic Data Structure for Efficient High Dimensional Nearest-Foreign-Neighbor Queries

      • T. Graf, V. Kamakoti, N. S. Janaki Latha, C. Pandu Rangan

      Pages 35-44

   4. Space-Efficient Algorithms for Approximating Polygonal Curves in Two Dimensional Space

      • Danny Z. Chen, Ovidiu Daescu

      Pages 45-55

   5. Parallel Geometric Algorithms in Coarse-Grain Network Models

      • Mikhail J. Atallah, Danny Z. Chen

      Pages 55-65

4. Algorithms and Data Structures

   1. On the Bahncard Problem

      • Rudolf Fleischer

      Pages 65-74

   2. The Ultimate Strategy to Search on m Rays?

      • Alejandro López-Ortiz, Sven Schuierer

      Pages 75-85

   3. Better Approximation of Diagonal-Flip Transformation and Rotation Transformation

      • Ming Li, Louxin Zhang

      Pages 85-94

   4. A Cost Optimal Parallel Algorithm for Computing Force Field in N-Body Simulations

      • Guoliang Xue

      Pages 95-104

   5. Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT

      • Mutsunori Yagiura, Toshihide Ibaraki

      Pages 105-116

   6. Algorithms for Almost-Uniform Generation with an Unbiased Binary Source

      • Ömer Eğecioğlu, Marcus Peinado

      Pages 117-126

   7. Improved Algorithms for Chemical Threshold Testing Problems

      • Annalisa De Bonis, Luisa Gargano, Ugo Vaccaro

      Pages 127-137

   8. Min-Max-Boundary Domain Decomposition

      • Marcos Kiwi, Daniel A. Spielman, Shang-Hua Teng

      Pages 137-147

5. Computational Complexity

   1. On Boolean Lowness and Boolean Highness

      • Steffen Reith, Klaus W. Wagner

      Pages 147-157

   2. The Inherent Dimension of Bounded Counting Classes

      • Ulrich Hertrampf

      Pages 157-166

The papers in this volume were selected for presentation at the Fourth Annual International Computing and Combinatorics Conference (COCOON’98), held on August 12–14, 1998, in Taipei. The topics cover most aspects of theoretical computer science and combinatorics related to computing. Submissions to the conference this year was only conducted electronically. Thanks to the excellent software developed by the system team of the Institute of Information Science, we were able to make virtually all communications through the World Wide Web. A total of 69 papers was submitted in time to be considered, of which 36 papers were accepted for presentation at the conference. In addition to these contributed papers, the conference also included four invited presentations by Christo Papadimitriou, Michael Fishcher, Fan Chung Graham and Rao Kosaraju. It is expected that most of the accepted papers will appear in a more complete form in scienti?c journals. Moreover, selected papers will appear in a special issue of Theoretical Computer Science. We thank all program committee members, their support sta? and referees for excellent work within demanding time constraints. We thank all authors who submitted papers for consideration. We are especially grateful to our colleagues who worked hard and o?ered widely di?ering talents to make the conference both possible and enjoyable. August 1998 Wen-Lian Hsu and Ming-Yang Kao Program Co-chairs COCOON’98 Organization COCOON’98 is organized by the Institute of Information Science, Academia Sinica, Taipei, Taiwan, ROC and in cooperation with Institute of Information and Computing Machinery (IICM), Taiwan, ROC.

• Algorthms
• Distributed Algorithms
• Graph Computations
• Switching
• algorithms
• combinatorics
• complexity
• computational geometry
• data structures
• geometry
• algorithm analysis and problem complexity

• Institute of Information Science, Academia Sinica, Nankang, Taipei, Taiwan

  Wen-Lian Hsu

• Department of Computer Science, Yale University, New Haven, USA

  Ming-Yang Kao

Policies and ethics