## Computing and Combinatorics: 14th International Conference, COCOON 2008 Dalian, China, June 27-29, 2008, ProceedingsThe 14th Annual International Computing and Combinatorics Conference, CO- COON2008, tookplaceinDalian, China, June27-29,2008.PastCOCOONc- ferences were held in Xi'an (1995), Hong Kong (1996), Shanghai (1997), Taipei (1998), Tokyo (1999), Sydney (2000), Guilin (2001), Singapore (2002), Montana (2003), Jeju Island (2004), Kunming (2005), Taipei (2006), and Alberta (2007). COCOON 2008 provided a forum for researchers working in the areas of - gorithms, theory of computation, computational complexity, and combinatorics related to computing. The Program Committee received 172 submissions from 26 countries and regions: Canada, Australia, Austria, Brazil, China, Denmark, France, Germany, HongKong, Hungary, India, Iran, Israel, Japan, Korea, Mexico, Morocco, Netherlands, Pakistan, Singapore, Spain, Switzerland, Taiwan, Ukraine, the UK, and USA. With the help of 116 external referees, each submission was reviewed by at least two Program Committee members or external referees. Of the 172 subm- sions,66paperswereselectedforpresentationintheconferenceandareincluded in this volume. Some of these will be selected for publication in a special issue of Algorithmica and a special issue of the Journal of Combinatorial Optimization under the standard refereeing procedure. In addition to the selected papers, the conference also included two invited presentations by Der-Tsai Lee (Academia Sinica, Taiwan) and Takao Nishizeki (Tohoku University, Japan). The best paper awards were given for "Visual Cryptography on Graphs" to Lu, Manchala and Ostrovsky, and for "A Linear Programming Duality - proach to Analyzing Strictly Nonblocking d-ary Multilog Networks under G- eral Crosstalk Constraints" to Ngo, Wang and Le. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Efficient Compression of Web Graphs | 1 |

Damaged BZip Files Are Difficult to Repair | 12 |

Isoperimetric Problem and Metaﬁbonacci Sequences | 22 |

On the Complexity of Equilibria Problems in AngelDaemon Games | 31 |

AverageCase Competitive Analyses for OneWay Trading | 41 |

On the Monotonicity of Weak Searching | 52 |

VC Dimension Bounds for Analytic Algebraic Computations | 62 |

Resource Bounded Frequency Computations with Three Errors | 72 |

Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance | 352 |

On Center Regions and Balls Containing Many Points | 363 |

On Unfolding 3D Lattice Polygons and 2D Orthogonal Trees | 374 |

New Algorithms for Online Rectangle Filling with kLookahead | 385 |

Geometric Spanner of Objects under L₁ Distance | 395 |

StarShaped Drawings of Graphs with Fixed Embedding and Concave Corner Constraints | 405 |

A New Characterization of P₆Free Graphs | 415 |

Maximum Connected Domatic Partition of Directed Path Graphs with Single Junction | 425 |

A Sublinear Time Randomized Algorithm for Coset Enumeration in the Black Box Model | 82 |

Smallest Formulas for Parity of 2K Variables Are Essentially Unique | 92 |

Counting Polycubes without the Dimensionality Curse | 100 |

Polychromatic Colorings of nDimensional GuillotinePartitions | 110 |

The Computational Complexity of Link Building | 119 |

Improved Parameterized Algorithms for Weighted 3Set Packing | 130 |

Structural Identiﬁability in LowRank Matrix Factorization | 140 |

Complexity of Counting the Optimal Solutions | 149 |

The Orbit Problem Is in the GapL Hierarchy | 160 |

Quantum Separation of Local Search and Fixed Point Computation | 170 |

Multiparty Quantum Communication Complexity with Routed Messages | 180 |

Monotone DNF Formula That Has a Minimal or Maximal Number of Satisfying Assignments | 191 |

Approximating Alternative Solutions | 204 |

Dimensions of Points in Selfsimilar Fractals | 215 |

Visual Cryptography on Graphs | 225 |

Algebraic Cryptanalysis of CTRU Cryptosystem | 235 |

Detecting Community Structure by Network Vectorization | 245 |

Complexity and Binding Pairs | 255 |

Complexity of a CollisionAware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis | 265 |

Genome Halving under DCJ Revisited | 276 |

Haplotype Inferring Via GalledTree Networks Is NPComplete | 287 |

Adjacent Swaps on Strings | 299 |

Efficient Algorithms for SNP Haplotype Block Selection Problems | 309 |

Sequence Alignment Algorithms for RunLengthEncoded Strings | 319 |

A 225Approximation Algorithm for CutandPaste Sorting of Unsigned Circular Permutations | 331 |

A Practical Exact Algorithm for the Individual Haplotyping Problem MECGI | 342 |

Efficient Algorithms for the k Smallest Cuts Enumeration | 434 |

Covering Directed Graphs by InTrees | 444 |

On Listing Sampling and Counting the Chordal Graphs with Edge Constraints | 458 |

Probe Ptolemaic Graphs | 468 |

Diagnosability of TwoMatching Composition Networks | 478 |

The Iterated Restricted Immediate Snapshot Model | 487 |

Finding Frequent Items in a Turnstile Data Stream | 498 |

A Linear Programming Duality Approach to Analyzing Strictly Nonblocking dary Multilog Networks under General Crosstalk Constraints | 510 |

Optimal Tree Structures for Group Key Tree Management Considering Insertion and Deletion Cost | 521 |

Throughput Maximization with Traffic Proﬁle in Wireless Mesh Network | 531 |

Joint Topology Control and Power Conservation for Wireless Sensor Networks Using Transmit Power Adjustment | 541 |

6 + εApproximation for Minimum Weight Dominating Set in Unit Disk Graphs | 551 |

Spectrum Bidding in Wireless Networks and Related | 558 |

1 + ρApproximation for SelectedInternal Steiner Minimum Tree | 568 |

Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities | 577 |

Spreading Messages | 587 |

On Some City Guarding Problems | 600 |

Optimal Insertion of a Segment Highway in a City Metric | 611 |

Approximating the Generalized Capacitated TreeRouting Problem | 621 |

TwoAgent Scheduling with Linear Deteriorating Jobs on a Single Machine | 642 |

A TwoStage Flexible Flowshop Problem with Deterioration | 651 |

A Lower Bound for the OnLine Preemptive Machine Scheduling with ℓᵨ Norm | 661 |

The Coordination of Two Parallel Machines Scheduling and Batch Deliveries | 670 |

678 | |

### Other editions - View all

### Common terms and phrases

adjacent algorithm approximation assume batch Berlin Heidelberg 2008 bipartite block cell chordal chordal graphs colors column complexity Computer Science connected consider construct contains corresponding cycle deﬁned Deﬁnition deletion denote diﬀerent directed graph dominating set edge eﬃcient elements exists ﬁnd ﬁnding ﬁnite ﬁrst ﬁxed ﬂow formula function G V,E genome given graph G guards haplotype in-trees input integer intersection lattice Lemma linear LNCS lower bound machine matrix maximum minimal minimum monotone node NP-complete NP-hard obtained optimal output PageRank pair paper partition path permutation plane graph polycube polygon polynomial problem Proof protein prove quantum query complexity random result satisﬁes schedule segment sequence solution solve Springer Steiner minimum tree Steiner points Steiner tree string subgraph subset Theorem undirected variables VC dimension vector vertex vertices Voronoi diagram Wang Eds weak searching Web graph weight