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

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