Computing and Combinatorics [electronic resource] : 7th Annual International Conference, COCOON 2001 Guilin, China, August 20–23, 2001 Proceedings /

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.

Bibliographic Details

Main Authors:	Wang, Jie. editor., SpringerLink (Online service)
Format:	Texto biblioteca
Language:	eng
Published:	Berlin, Heidelberg : Springer Berlin Heidelberg, 2001
Subjects:	Mathematics., Computer communication systems., Computers., Algorithms., Computer science, Computer graphics., Discrete mathematics., Discrete Mathematics., Theory of Computation., Algorithm Analysis and Problem Complexity., Discrete Mathematics in Computer Science., Computer Graphics., Computer Communication Networks.,
Online Access:	http://dx.doi.org/10.1007/3-540-44679-6
Tags:	Add Tag No Tags, Be the first to tag this record!