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

ISBN-13: 9783540424949 / Angielski / Miękka / 2001 / 606 str.

J. Wang; Jie Wang

Opis

This volume 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 modelling, and computability.

Spis treści

Complexity Theory.- Complete Problems for Valiant’s Class of qp-Computable Families of Polynomials.- Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n 4.03).- On Universally Polynomial Context-Free Languages.- Separating Oblivious and Non-oblivious BPs.- Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws.- Algebraic Properties for P-Selectivity.- Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM.- Computational Biology.- Enhanced Sequence Reconstruction with DNA Microarray Application.- Non-approximability of Weighted Multiple Sequence Alignment.- A Greedy Algorithm for Optimal Recombination.- Computational Geometry.- Generating Well-Shaped d-dimensional Delaunay Meshes.- Towards Compatible Triangulations.- An Improved Upper Bound on the Size of Planar Convex-Hulls.- On the Planar Two-Watchtower Problem.- Efficient Generation of Triconnected Plane Triangulations.- Packing Two Disks into a Polygonal Environment.- Maximum Red/Blue Interval Matching with Application.- Computing Farthest Neighbors on a Convex Polytope.- Finding an Optimal Bridge between Two Polygons.- How Good Is Sink Insertion?.- Polynomial Time Algorithms for Three-Label Point Labeling.- Approximation Algorithms for the Watchman Route and Zookeeper’s Problems.- Data Structures and Algorithms.- PC-Trees vs. PQ-Trees.- Stacks versus Deques.- Optimizing a Computational Method for Length Lower Bounds for Reflecting Sequences.- Games and Combinatorics.- Competitive Facility Location along a Highway.- Membership for Core of LP Games and Other Games.- Strong Solutions to the Identification Problem.- Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF(2m)1.- Graph Algorithms and Complexity.- A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms.- Finding the Most Vital Node of a Shortest Path.- Algorithm for the Cost Edge-Coloring of Trees.- Counting H-Colorings of Partial k-Trees.- A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph.- Graph Separators: A Parameterized View.- On Assigning Prefix Free Codes to the Vertices of a Graph.- A New Measure of Edit Distance between Labeled Trees.- A Highly Efficient Algorithm to Determine Bicritical Graphs.- Graph Drawing.- Layered Drawings of Graphs with Crossing Constraints.- On the Validity of Hierarchical Decompositions.- Graph Theory.- Lower Bounds on the Minus Domination and k-Subdomination Numbers.- Edge Connectivity vs Vertex Connectivity in Chordal Graphs.- Changing the Diameter of Graph Products.- Plane Graphs with Acyclic Complex.- On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz Digraphs.- A Notion of Cross-Perfect Bipartite Graphs.- Some Results on Orthogonal Factorizations.- Cluttered Orderings for the Complete Graph.- Online Algorithms.- Improved On-Line Stream Merging: From a Restricted to a General Setting.- On-Line Deadline Scheduling on Multiple Resources.- Competitive Online Scheduling with Level of Service.- On-Line Variable Sized Covering.- Randomized and Average-Case Algorithms.- On Testing for Zero Polynomials by a Set of Points with Bounded Precision.- A Randomized Algorithm for Gossiping in Radio Networks.- Deterministic Application of Grover’s Quantum Search Algorithm.- Random Instance Generation for MAX 3SAT.- Steiner Trees.- The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Points.- AnFPTAS forWeight-Constrained SteinerTrees in Series-Parallel Graphs.- Systems Algorithms and Modeling.- Decidable Approximations on Generalized and Parameterized Discrete Timed Automata.- Multiplicative Adaptive Algorithms for User Preference Retrieval.- Parametric Scheduling for Network Constraints.- A Logical Framework for Knowledge Sharing in Multi-agent Systems.- A Lockout Avoidance Algorithm without Using Time-Stamps for the k-Exclusion Problem.- Computability.- Prefix-Free Languages and Initial Segments of Computably Enumerable Degrees.- Weakly Computable Real Numbers and Total Computable Real Functions.- Turing Computability of a Nonlinear Schrödinger Propagator.