Computing and Combinatorics: 16th Annual International Conference, Cocoon 2010, Nha Trang, Vietnam, July 19-21, 2010 Proceedings

ISBN-13: 9783642140303 / Angielski / Miękka / 2010 / 553 str.

My T. Thai; Sartaj Sahni

Opis

Constitutes the proceedings of the 16th Annual International Conference on Computing and Combinatorics, held in Nha Trang, Vietnam, in July 2010.

Spis treści

Invited Talks.- Understanding and Inductive Inference.- Computing with Cells: Membrane Systems.- Complexity and Inapproximability.- Boxicity and Poset Dimension.- On the Hardness against Constant-Depth Linear-Size Circuits.- A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model.- The Curse of Connectivity: t-Total Vertex (Edge) Cover.- Counting Paths in VPA Is Complete for #NC 1.- Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas.- Approximation Algorithms.- Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing.- Clustering with or without the Approximation.- A Self-stabilizing 3-Approximation for the Maximum Leaf Spanning Tree Problem in Arbitrary Networks.- Approximate Weighted Farthest Neighbors and Minimum Dilation Stars.- Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs.- Graph Theory and Algorithms.- Maximum Upward Planar Subgraph of a Single-Source Embedded Digraph.- Triangle-Free 2-Matchings Revisited.- The Cover Time of Deterministic Random Walks.- Finding Maximum Edge Bicliques in Convex Bipartite Graphs.- A Note on Vertex Cover in Graphs with Maximum Degree 3.- Computing Graph Spanners in Small Memory: Fault-Tolerance and Streaming.- Factorization of Cartesian Products of Hypergraphs.- Graph Drawing and Coloring.- Minimum-Segment Convex Drawings of 3-Connected Cubic Plane Graphs.- On Three Parameters of Invisibility Graphs.- Imbalance Is Fixed Parameter Tractable.- The Ramsey Number for a Linear Forest versus Two Identical Copies of Complete Graphs.- Computational Geometry.- Optimal Binary Space Partitions in the Plane.- Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems.- Effect of Corner Information in Simultaneous Placement of K Rectangles and Tableaux.- Detecting Areas Visited Regularly.- Tile-Packing Tomography Is -hard.- The Rectilinear k-Bends TSP.- Tracking a Generator by Persistence.- Auspicious Tatami Mat Arrangements.- Automata, Logic, Algebra and Number Theory.- Faster Generation of Shorthand Universal Cycles for Permutations.- The Complexity of Word Circuits.- On the Density of Regular and Context-Free Languages.- Extensions of the Minimum Cost Homomorphism Problem.- The Longest Almost-Increasing Subsequence.- Universal Test Sets for Reversible Circuits.- Approximate Counting with a Floating-Point Counter.- Network Optimization and Scheduling Algorithm.- Broadcasting in Heterogeneous Tree Networks.- Contention Resolution in Multiple-Access Channels: k-Selection in Radio Networks.- Online Preemptive Scheduling with Immediate Decision or Notification and Penalties.- Computational Biology and Bioinformatics.- Discovering Pairwise Compatibility Graphs.- Near Optimal Solutions for Maximum Quasi-bicliques.- Fast Coupled Path Planning: From Pseudo-Polynomial to Polynomial.- Constant Time Approximation Scheme for Largest Well Predicted Subset.- On Sorting Permutations by Double-Cut-and-Joins.- A Three-String Approach to the Closest String Problem.- A 2k Kernel for the Cluster Editing Problem.- Data Structure and Sampling Theory.- On the Computation of 3D Visibility Skeletons.- The Violation Heap: A Relaxed Fibonacci-Like Heap.- Threshold Rules for Online Sample Selection.- Heterogeneous Subset Sampling.- Cryptography, Security, Coding and Game Theory.- Identity-Based Authenticated Asymmetric Group Key Agreement Protocol.- Zero-Knowledge Argument for Simultaneous Discrete Logarithms.- Directed Figure Codes: Decidability Frontier.