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

Front Matter....Pages -
Understanding and Inductive Inference....Pages 1-1
Computing with Cells: Membrane Systems....Pages 2-2
Boxicity and Poset Dimension....Pages 3-12
On the Hardness against Constant-Depth Linear-Size Circuits....Pages 13-22
A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model....Pages 23-33
The Curse of Connectivity: t -Total Vertex (Edge) Cover....Pages 34-43
Counting Paths in VPA Is Complete for # NC 1 ....Pages 44-53
Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas....Pages 54-59
Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing....Pages 60-69
Clustering with or without the Approximation....Pages 70-79
A Self-stabilizing 3-Approximation for the Maximum Leaf Spanning Tree Problem in Arbitrary Networks....Pages 80-89
Approximate Weighted Farthest Neighbors and Minimum Dilation Stars....Pages 90-99
Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs....Pages 100-109
Maximum Upward Planar Subgraph of a Single-Source Embedded Digraph....Pages 110-119
Triangle-Free 2-Matchings Revisited....Pages 120-129
The Cover Time of Deterministic Random Walks....Pages 130-139
Finding Maximum Edge Bicliques in Convex Bipartite Graphs....Pages 140-149
A Note on Vertex Cover in Graphs with Maximum Degree 3....Pages 150-159
Computing Graph Spanners in Small Memory: Fault-Tolerance and Streaming....Pages 160-172
Factorization of Cartesian Products of Hypergraphs....Pages 173-181
Minimum-Segment Convex Drawings of 3-Connected Cubic Plane Graphs....Pages 182-191
On Three Parameters of Invisibility Graphs....Pages 192-198
Imbalance Is Fixed Parameter Tractable....Pages 199-208
The Ramsey Number for a Linear Forest versus Two Identical Copies of Complete Graphs....Pages 209-215
Optimal Binary Space Partitions in the Plane....Pages 216-225
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems....Pages 226-234
Effect of Corner Information in Simultaneous Placement of K Rectangles and Tableaux....Pages 235-243
Detecting Areas Visited Regularly....Pages 244-253
Tile-Packing Tomography Is ${\\mathbb{NP}}$ -hard....Pages 254-263
The Rectilinear k -Bends TSP....Pages 264-277
Tracking a Generator by Persistence....Pages 278-287
Auspicious Tatami Mat Arrangements....Pages 288-297
Faster Generation of Shorthand Universal Cycles for Permutations....Pages 298-307
The Complexity of Word Circuits....Pages 308-317
On the Density of Regular and Context-Free Languages....Pages 318-327
Extensions of the Minimum Cost Homomorphism Problem....Pages 328-337
The Longest Almost-Increasing Subsequence....Pages 338-347
Universal Test Sets for Reversible Circuits....Pages 348-357
Approximate Counting with a Floating-Point Counter....Pages 358-367
Broadcasting in Heterogeneous Tree Networks....Pages 368-377
Contention Resolution in Multiple-Access Channels: k -Selection in Radio Networks....Pages 378-388
Online Preemptive Scheduling with Immediate Decision or Notification and Penalties....Pages 389-398
Discovering Pairwise Compatibility Graphs....Pages 399-408
Near Optimal Solutions for Maximum Quasi-bicliques....Pages 409-418
Fast Coupled Path Planning: From Pseudo-Polynomial to Polynomial....Pages 419-428
Constant Time Approximation Scheme for Largest Well Predicted Subset....Pages 429-438
On Sorting Permutations by Double-Cut-and-Joins....Pages 439-448
A Three-String Approach to the Closest String Problem....Pages 449-458
A 2 k Kernel for the Cluster Editing Problem....Pages 459-468
On the Computation of 3D Visibility Skeletons....Pages 469-478
The Violation Heap: A Relaxed Fibonacci-Like Heap....Pages 479-488
Threshold Rules for Online Sample Selection....Pages 489-499
Heterogeneous Subset Sampling....Pages 500-509
Identity-Based Authenticated Asymmetric Group Key Agreement Protocol....Pages 510-519
Zero-Knowledge Argument for Simultaneous Discrete Logarithms....Pages 520-529
Directed Figure Codes: Decidability Frontier....Pages 530-539
Back Matter....Pages -