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

Christos H. Papadimitriou (auth.), Ding-Zhu Du, Peter Eades, Vladimir Estivill-Castro, Xuemin Lin, Arun Sharma (eds.)3540677879, 9783540677871

This book constitutes the refereed proceedings of the 6th Annual International Conference on Computing and Combinatorics, COCOON 2000, held in Sydney, Australia in July 2000.
The 44 revised full papers presented together with two invited contributions were carefully reviewed and selected from a total of 81 submissions. The book offers topical sections on computational geometry; graph drawing; graph theory and algorithms; complexity, discrete mathematics, and number theory; online algorithms; parallel and distributed computing; combinatorial optimization; data structures and computational biology; learning and cryptography; and automata and quantum computing.

---

Table of contents :
Theoretical Problems Related to the Internet….Pages 1-2
Recent Progress and Prospects for Integer Factorisation Algorithms….Pages 3-22
Approximating Uniform Triangular Meshes in Polygons….Pages 23-33
Maximum Induced Matchings of Random Cubic Graphs….Pages 34-43
A Duality between Small-Face Problems in Arrangements of Lines and Heilbronn-Type Problems….Pages 44-53
On Local Transformation of Polygons with Visibility Properties….Pages 54-63
Embedding Problems for Paths with Direction Constrained Edges….Pages 64-73
Characterization of Level Non-planar Graphs by Minimal Patterns….Pages 74-84
Rectangular Drawings of Plane Graphs Without Designated Corners….Pages 85-94
Computing Optimal Embeddings for Planar Graphs….Pages 95-104
Approximation Algorithms for Independent Sets in Map Graphs….Pages 105-114
Hierarchical Topological Inference on Planar Disc Maps….Pages 115-125
Efficient Algorithms for the Minimum Connected Domination on Trapezoid Graphs….Pages 126-136
Parameterized Complexity of Finding Subgraphs with Hereditary Properties….Pages 137-147
Some Results on Tries with Adaptive Branching….Pages 148-158
Optimal Coding with One Asymmetric Error: Below the Sphere Packing Bound….Pages 159-169
Closure Properties of Real Number Classes under Limits and Computable Operators….Pages 170-179
A Characterization of Graphs with Vertex Cover Six….Pages 180-192
On the Monotonicity of Minimum Diameter with Respect to Order and Maximum Out-Degree….Pages 193-201
Online Independent Sets….Pages 202-209
Two-Dimensional On-Line Bin Packing Problem with Rotatable Items….Pages 210-220
Better Bounds on the Accommodating Ratio for the Seat Reservation Problem….Pages 221-231
Ordinal On-Line Scheduling on Two Uniform Machines….Pages 232-241
Agents, Distributed Algorithms, and Stabilization….Pages 242-251
A Fast Sorting Algorithm and Its Generalization on Broadcast Communications….Pages 252-261
Efficient List Ranking Algorithms on Reconfigurable Mesh….Pages 262-271
Tripods Do Not Pack Densely….Pages 272-280
An Efficient k Nearest Neighbor Searching Algorithm for a Query Line….Pages 281-290
Tetrahedralization of Two Nested Convex Polyhedra….Pages 291-298
Efficient Algorithms for Two-Center Problems for a Convex Polygon….Pages 299-309
On Computation of Arbitrage for Markets with Friction….Pages 310-319
On Some Optimization Problems in Obnoxious Facility Location….Pages 320-329
Generating Necklaces and Strings with Forbidden Substrings….Pages 330-339
Optimal Labelling of Point Features in the Slider Model….Pages 340-350
Mappings for Conflict-Free Access of Paths in Elementary Data Structures….Pages 351-361
Theory of Trinomial Heaps….Pages 362-372
Polyhedral Aspects of the Consecutive Ones Problem….Pages 373-382
The Complexity of Physical Mapping with Strict Chimerism….Pages 383-395
Logical Analysis of Data with Decomposable Structures….Pages 396-406
Learning from Approximate Data….Pages 407-415
A Combinatorial Approach to Asymmetric Traitor Tracing….Pages 416-425
Removing Complexity Assumptions from Concurrent Zero-Knowledge Proofs….Pages 426-435
One-Way Probabilistic Reversible and Quantum One-Counter Automata….Pages 436-446
Similarity Enrichment in Image Compression through Weighted Finite Automata….Pages 447-456
On the Power of Input-Synchronized Alternating Finite Automata….Pages 457-466
Ordered Quantum Branching Programs Are More Powerful than Ordered Probabilistic Branching Programs under a Bounded-Width Restriction….Pages 467-476