Computing and Combinatorics: 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26-28, 2000 Proceedings

Front Cover
Ding-Zhu Du, Peter Eades, Vladimir Estivill-Castro, Xuemin Lin, Arun Sharma
Springer Science & Business Media, Jul 12, 2000 - Computers - 478 pages
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
Author Index
477
Copyright

Other editions - View all

Common terms and phrases