## Computing and Combinatorics: 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26-28, 2000 ProceedingsDing-Zhu Du, Peter Eades, Vladimir Estivill-Castro, Xuemin Lin, Arun Sharma The papers in this volume were selected for presentation at the 6th Annual International Computing and Combinatorics Conference (COCOON2000), in Sydney, Australia from July 26 - 28, 2000. The topics cover many areas in t- oretical computer science and combinatorial optimization. There were 81 high quality papers submitted to COCOON2000. Each paper was reviewed by at least three program committee members, and the 44 papers were selected. It is expected that most of them will appear in a more complete form in scientic journals. In addition to the selected papers, the volume also contains the papers from two invited keynote speeches by Christos Papad- itriou and Richard Brent. This year the Hao Wang Award was given to honor the paper judged by the programcommittee to have the greatest merit. The recipient is \Approximating Uniform TriangularMeshes in Polygons"byFranz Aurenhammer, NaokiKatoh, Hiromichi Kojima, Makoto Ohsaki, and Yinfeng Xu. The rst Best Young - searcher paper award was given to William Duckworth for his paper \Maximum Induced Matchings of Random Cubic Graphs." We wish to thank all who have made this meeting possible: the authors for submitting papers, the program committee members and the external referees, sponsors, the local organizers, ACM SIGACT for handling electronic subm- sions, Springer-Verlagfor their support, and Debbie Hatherellfor her assistance. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Theoretical Problems Related to the Internet | 1 |

Recent Progress and Prospects for Integer Factorisation Algorithms | 3 |

Approximating Uniform Triangular Meshes in Polygons | 23 |

Maximum Induced Matchings of Random Cubic Graphs | 34 |

A Duality between SmallFace Problems in Arrangements of Lines and HeilbronnType Problems | 44 |

On Local Transformation of Polygons with Visibility Properties | 54 |

Embedding Problems for Paths with Direction Constrained Edges | 64 |

Characterization of Level Nonplanar Graphs by Minimal Patterns | 74 |

A Fast Sorting Algorithm and Its Generalization on Broadcast Communications | 252 |

Efficient List Ranking Algorithms on Reconfigurable Mesh | 262 |

Tripods Do Not Pack Densely | 272 |

An Efficient k Nearest Neighbor Searching Algorithm for a Query Line | 281 |

Tetrahedralization of Two Nested Convex Polyhedra | 291 |

Efficient Algorithms for TwoCenter Problems for a Convex Polygon | 299 |

On Computation of Arbitrage for Markets with Friction | 310 |

On Some Optimization Problems in Obnoxious Facility Location | 320 |

Rectangular Drawings of Plane Graphs Without Designated Corners | 85 |

Computing Optimal Embeddings for Planar Graphs | 95 |

Approximation Algorithms for Independent Sets in Map Graphs | 105 |

Hierarchical Topological Inference on Planar Disc Maps | 115 |

Efficient Algorithms for the Minimum Connected Domination on Trapezoid Graphs | 126 |

Parameterized Complexity of Finding Subgraphs with Hereditary Properties | 137 |

Some Results on Tries with Adaptive Branching | 148 |

Below the Sphere Packing Bound | 159 |

Closure Properties of Real Number Classes under Limits and Computable Operators | 170 |

A Characterization of Graphs with Vertex Cover Six | 180 |

On the Monotonicity of Minimum Diameter with Respect to Order and Maximum OutDegree | 193 |

Online Independent Sets | 202 |

TwoDimensional OnLine Bin Packing Problem with Rotatable Items | 210 |

Better Bounds on the Accommodating Ratio for the Seat Reservation Problem | 221 |

Ordinal OnLine Scheduling on Two Uniform Machines | 232 |

Agents Distributed Algorithms and Stabilization | 242 |

Generating Necklaces and Strings with Forbidden Substrings | 330 |

Optimal Labelling of Point Features in the Slider Model | 340 |

Mappings for ConflictFree Access of Paths in Elementary Data Structures | 351 |

Theory of Trinomial Heaps | 362 |

Polyhedral Aspects of the Consecutive Ones Problem | 373 |

The Complexity of Physical Mapping with Strict Chimerism | 383 |

Logical Analysis of Data with Decomposable Structures | 396 |

Learning from Approximate Data | 407 |

A Combinatorial Approach to Asymmetric Traitor Tracing | 416 |

Removing Complexity Assumptions from Concurrent ZeroKnowledge Proofs | 426 |

OneWay Probabilistic Reversible and Quantum OneCounter Automata | 436 |

Similarity Enrichment in Image Compression through Weighted Finite Automata | 447 |

On the Power of InputSynchronized Alternating Finite Automata | 457 |

Ordered Quantum Branching Programs Are More Powerful than Ordered Probabilistic Branching Programs under a BoundedWidth Restriction | 467 |

477 | |

### Other editions - View all

### Common terms and phrases

3-legged cycle assume Berlin Heidelberg 2000 biconnected graph boolean called combinatorial competitive ratio computable real function Computer Science consider construction contains convex polygon corresponding cubic graph deﬁned denote digraph edge embedding exists extreme level field sieve finite function given graph drawing graph G independent set induced matching induced subgraph input integer k–Vertex Cover labels least Lemma level non-planar level planar linear LNCS logn lower bound map graphs matrix maximum minimal minimum node NP-complete NP-hard obtain on-line algorithm one-way i-SAFA online algorithm optimal pair paper parameter path plane graph polynomial problem Proc processors proof system random real numbers rectangular drawing recursive result root satisfies segment sequence solution strings subgraph subset successful broadcast synchronizing Theorem triangle upper bound vector vertex vertex cover vertices of degree Voronoi Voronoi diagram weight zk proof