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.
Author(s): Christos H. Papadimitriou (auth.), Wen-Lian Hsu, Ming-Yang Kao (eds.)
Series: Lecture Notes in Computer Science 1449
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1998
Language: English
Pages: 372
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Data Structures; Computer Communication Networks; Combinatorics
Algorithmic Approaches to Information Retrieval and Data Mining....Pages 1-1
Combinatorial Problems Arising in Massive Data Sets....Pages 2-2
Estimating Parameters of Monotone Boolean Functions....Pages 3-3
De-amortization of Algorithms....Pages 4-14
On Computing New Classes of Optimal Triangulations with Angular Constraints....Pages 15-24
Maximum Weight Triangulation and Its Application on Graph Drawing....Pages 25-34
The Colored Sector Search Tree: A Dynamic Data Structure for Efficient High Dimensional Nearest-Foreign-Neighbor Queries....Pages 35-44
Space-Efficient Algorithms for Approximating Polygonal Curves in Two Dimensional Space....Pages 45-55
Parallel Geometric Algorithms in Coarse-Grain Network Models....Pages 55-65
On the Bahncard Problem....Pages 65-74
The Ultimate Strategy to Search on m Rays?....Pages 75-85
Better Approximation of Diagonal-Flip Transformation and Rotation Transformation....Pages 85-94
A Cost Optimal Parallel Algorithm for Computing Force Field in N-Body Simulations....Pages 95-104
Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT....Pages 105-116
Algorithms for Almost-Uniform Generation with an Unbiased Binary Source....Pages 117-126
Improved Algorithms for Chemical Threshold Testing Problems....Pages 127-137
Min-Max-Boundary Domain Decomposition....Pages 137-147
On Boolean Lowness and Boolean Highness....Pages 147-157
The Inherent Dimension of Bounded Counting Classes....Pages 157-166
An Exact Characterization of Symmetric Functions in q AC 0 [2]....Pages 167-173
Robust Reductions....Pages 174-183
Approaches to Effective Semi-continuity of Real Functions....Pages 184-193
On the Power of Additive Combinatorial Search Model....Pages 194-203
The Number of Rearrangements in a 3-stage Clos Network Using an Auxiliary Switch....Pages 204-212
Lower Bounds for Wide-Sense Non-blocking Clos Network....Pages 213-218
Multirate Multicast Switching Networks....Pages 219-228
Efficient Randomized Routing Algorithms on the Two-Dimensional Mesh of Buses....Pages 229-240
Executing Divisible Jobs on a Network with a Fixed Number of Processors....Pages 241-250
On the Ádám Conjecture on Circulant Graphs....Pages 251-260
Proof of Toft’s Conjecture: Every Graph Containing No Fully Odd K 4 Is 3-Colorable....Pages 261-268
A New Family of Optimal 1-Hamiltonian Graphs with Small Diameter....Pages 269-278
A Linear-Time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree....Pages 279-289
A Graph Optimization Problem in Virtual Colonoscopy....Pages 289-298
Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices....Pages 299-308
An Optimal Algorithm for Finding the Minimum Cardinality Dominating Set on Permutation Graphs....Pages 309-318
Similarity in Two-Dimensional Strings....Pages 319-328
On Multi-dimensional Hilbert Indexings....Pages 329-339
Combinatorial Properties of Classes of Functions Hard to Compute in Constant Depth....Pages 339-348
Eulerian Secret Key Exchange....Pages 349-360
One-Time Tables for Two-Party Computation....Pages 361-370
