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

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