Computing and Combinatorics: 7th Annual International Conference, COCOON 2001 Guilin, China, August 20–23, 2001 Proceedings

Markus Bläser (auth.), Jie Wang (eds.)3540424946, 9783540424949

This book constitutes the refereed proceedings of the 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, held in Guilin, China, in August 2001.
The 50 revised full papers and 16 short papers presented were carefully reviewed and selected from 97 submissions. The papers are organized in topical sections on complexity theory, computational biology, computational geometry, data structures and algorithms, games and combinatorics, graph algorithms and complexity, graph drawing, graph theory, online algorithms, randomized and average-case algorithms, Steiner trees, systems algorithms and modeling, and computability.

---

Table of contents :
Complete Problems for Valiant’s Class of qp-Computable Families of Polynomials….Pages 1-10
Log-Space Constructible Universal Traversal Sequences for Cycles of Length O( n 4.03 )….Pages 11-20
On Universally Polynomial Context-Free Languages….Pages 21-27
Separating Oblivious and Non-oblivious BPs….Pages 28-38
Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws….Pages 39-48
Algebraic Properties for P-Selectivity….Pages 49-58
Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM….Pages 59-63
Enhanced Sequence Reconstruction with DNA Microarray Application….Pages 64-74
Non-approximability of Weighted Multiple Sequence Alignment….Pages 75-85
A Greedy Algorithm for Optimal Recombination….Pages 86-90
Generating Well-Shaped d -dimensional Delaunay Meshes….Pages 91-100
Towards Compatible Triangulations….Pages 101-110
An Improved Upper Bound on the Size of Planar Convex-Hulls….Pages 111-120
On the Planar Two-Watchtower Problem….Pages 121-130
Efficient Generation of Triconnected Plane Triangulations….Pages 131-141
Packing Two Disks into a Polygonal Environment….Pages 142-149
Maximum Red/Blue Interval Matching with Application….Pages 150-158
Computing Farthest Neighbors on a Convex Polytope….Pages 159-169
Finding an Optimal Bridge between Two Polygons….Pages 170-180
How Good Is Sink Insertion?….Pages 181-190
Polynomial Time Algorithms for Three-Label Point Labeling….Pages 191-200
Approximation Algorithms for the Watchman Route and Zookeeper’s Problems….Pages 201-206
PC -Trees vs. PQ -Trees….Pages 207-217
Stacks versus Deques….Pages 218-227
Optimizing a Computational Method for Length Lower Bounds for Reflecting Sequences….Pages 228-236
Competitive Facility Location along a Highway….Pages 237-246
Membership for Core of LP Games and Other Games….Pages 247-256
Strong Solutions to the Identification Problem….Pages 257-261
Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF(2 m ) 1 ….Pages 262-267
A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms….Pages 268-277
Finding the Most Vital Node of a Shortest Path….Pages 278-287
Algorithm for the Cost Edge-Coloring of Trees….Pages 288-297
Counting H -Colorings of Partial k -Trees….Pages 298-307
A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph….Pages 308-317
Graph Separators: A Parameterized View….Pages 318-327
On Assigning Prefix Free Codes to the Vertices of a Graph….Pages 328-337
A New Measure of Edit Distance between Labeled Trees….Pages 338-348
A Highly Efficient Algorithm to Determine Bicritical Graphs….Pages 349-356
Layered Drawings of Graphs with Crossing Constraints….Pages 357-367
On the Validity of Hierarchical Decompositions….Pages 368-374
Lower Bounds on the Minus Domination and k -Subdomination Numbers….Pages 375-383
Edge Connectivity vs Vertex Connectivity in Chordal Graphs….Pages 384-389
Changing the Diameter of Graph Products….Pages 390-394
Plane Graphs with Acyclic Complex….Pages 395-399
On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz Digraphs….Pages 400-408
A Notion of Cross-Perfect Bipartite Graphs….Pages 409-413
Some Results on Orthogonal Factorizations….Pages 414-419
Cluttered Orderings for the Complete Graph….Pages 420-431
Improved On-Line Stream Merging: From a Restricted to a General Setting….Pages 432-442
On-Line Deadline Scheduling on Multiple Resources….Pages 443-452
Competitive Online Scheduling with Level of Service….Pages 453-462
On-Line Variable Sized Covering….Pages 463-472
On Testing for Zero Polynomials by a Set of Points with Bounded Precision….Pages 473-482
A Randomized Algorithm for Gossiping in Radio Networks….Pages 483-492
Deterministic Application of Grover’s Quantum Search Algorithm….Pages 493-501
Random Instance Generation for MAX 3SAT….Pages 502-508
The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Points….Pages 509-518
AnFPTAS forWeight-Constrained SteinerTrees in Series-Parallel Graphs….Pages 519-528
Decidable Approximations on Generalized and Parameterized Discrete Timed Automata….Pages 529-539
Multiplicative Adaptive Algorithms for User Preference Retrieval….Pages 540-549
Parametric Scheduling for Network Constraints….Pages 550-560
A Logical Framework for Knowledge Sharing in Multi-agent Systems….Pages 561-570
A Lockout Avoidance Algorithm without Using Time-Stamps for the k -Exclusion Problem….Pages 571-575
Prefix-Free Languages and Initial Segments of Computably Enumerable Degrees….Pages 576-585
Weakly Computable Real Numbers and Total Computable Real Functions….Pages 586-595
Turing Computability of a Nonlinear Schrödinger Propagator….Pages 596-599