## Computing and Combinatorics: 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, ProceedingsThe Annual International Computing and Combinatorics Conference is an annual forum for exploring research, development, and novel applications of computing and combinatorics. It brings together researchers, professionals and industrial practitioners to interact and exchange knowledge, ideas and progress. Thetopics covermost aspects oftheoreticalcomputer scienceand combinatorics related to computing. The 13th Annual International Computing and Com- natorics Conference (COCOON 2007) was held in Ban?, Alberta during July 16–19, 2007. This was the ?rst time that COCOON was held in Canada. We received 165 submissions, among which 11 were withdrawn for various reasons. The remaining 154 submissions under full consideration came from 33 countries and regions: Australia, Brazil, Canada, China, the Czech Republic, Denmark, Finland, France, Germany, Greece, Hong Kong, India, Iran, Ireland, Israel, Italy, Japan, the Netherlands, Norway, Pakistan, Poland, Romania, R- sia, Slovakia, South Korea, Spain, Sweden, Switzerland, Taiwan, Turkey, the UK, the USA, and the US minor outlying islands. Afterasixweekperiodofcarefulreviewinganddiscussions,theprogramc- mittee accepted 51 submissions for oral presentation at the conference. Based on the a?liations, 1. 08 of the accepted papers were from Australia, 7. 67 from Canada, 3. 08 from China, 1 from the Czech Republic, 2 from Denmark, 1 from France, 5. 42 from Germany, 0. 08 from Greece, 2. 18 from Hong Kong, 0. 33 from India, 0. 17 from Ireland, 1. 83 from Israel, 1. 5fromItaly,2. 9 from Japan, 0. 17 from the Netherlands, 2. 67 from Norway, 0. |

### What people are saying - Write a review

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

### Contents

The Combinatorics of Sequencing the Corn Genome | 1 |

Online Frequency Assignment in Wireless Communication Networks | 2 |

Information Distance from a Question to an Answer | 3 |

A New Field Splitting Algorithm for IntensityModulated Radiation Therapy | 4 |

A New Recombination Lower Bound and the Minimum Perfect Phylogenetic Forest Problem | 16 |

SeedBased Exclusion Method for Noncoding RNA Gene Search | 27 |

Quartet Joining Method | 40 |

Integer Programming Formulations and Computations Solving Phylogenetic and Population Genetic Problems with Missing or Genotypic Data | 51 |

Efficient Testing of Forecasts | 285 |

Relevant Attributes Succeed? A FourierBased Characterization | 296 |

The Informational Content of Canonical Disjoint NPPairs | 307 |

On the Representations of NC and LogSpace Real Numbers | 318 |

Bounded Computable Enumerability and Hierarchy of Computably Enumerable Reals | 327 |

Streaming Algorithms Measured in Terms of the Computed Quantity | 338 |

A Randomized Approximation Algorithm for Parameterized 3D Matching Counting Problem | 349 |

Optimal Offline Extraction of Irredundant Motif Bases | 360 |

Improved Exact Algorithms for Counting 3 and 4Colorings | 65 |

Algorithms and Complexity | 75 |

Quadratic Kernelization for Convex Recoloring of Trees | 86 |

On the Number of Cycles in Planar Graphs | 97 |

An Improved Exact Algorithm for Cubic Graph TSP | 108 |

Do Short Cycles Help? | 118 |

Dimension Halfspaces and the Density of Hard Sets | 129 |

Isolation Concepts for Enumerating Dense Subgraphs | 140 |

Alignments with Nonoverlapping Moves Inversions and Tandem Duplications in On4 Time | 151 |

Counting Minimum Weighted Dominating Sets | 165 |

Randomized and Multiprocessor Cases | 176 |

About the Performance of Truthful Algorithms | 187 |

Volume Computation Using a Direct Monte Carlo Method | 198 |

Improved Throughput Bounds for InterferenceAware Routing in Wireless Networks | 210 |

Generating Minimal kVertex Connected Spanning Subgraphs | 222 |

Finding Many Optimal Paths Without Growing Any Optimal Path Trees | 232 |

Enumerating Constrained Noncrossing Geometric Spanning Trees | 243 |

Colored Simultaneous Geometric Embeddings | 254 |

Properties of Symmetric Incentive Compatible Auctions | 264 |

Finding Equilibria in Games of No Chance | 274 |

Linear Algorithm for Broadcasting in Unicyclic Graphs | 372 |

An Improved Algorithm for Online Unit Clustering | 383 |

Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs | 394 |

SingleEdge Monotonic Sequences of Graphs and LinearTime Algorithms for Minimal Completions and Deletions | 406 |

On the Hardness of Optimization in Power Law Graphs | 417 |

Algorithms for Core Stability Core Largeness Exactness and Extendability of Flow Games | 439 |

Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates | 448 |

On the Complexity of Finding an Unknown Cut Via Vertex Queries | 459 |

Resistant Polynomials and Stronger Lower Bounds for DepthThree Arithmetical Formulas | 470 |

An Improved Algorithm for Tree Edit Distance Incorporating Structural Linearity | 482 |

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats | 493 |

Priority Algorithms for the SubsetSum Problem | 504 |

Distributed Approximation Algorithms for Weighted Problems in MinorClosed Families | 515 |

A 1Local 139Competitive Algorithm for Multicoloring Hexagonal Graphs | 526 |

Improved Algorithms for Weighted and Unweighted Set Splitting Problems | 537 |

An 85Approximation Algorithm for a Hard Variant of Stable Marriage | 548 |

Approximation Algorithms for the Black and White Traveling Salesman Problem | 559 |

568 | |

### Other editions - View all

Computing and Combinatorics: 13th Annual International Conference, COCOON ... Guohui Lin Limited preview - 2007 |

### Common terms and phrases

approximation algorithms arbitrary assume Berlin Heidelberg 2007 bipartite bipartite graph Boolean function broadcast c-isolated canonical pairs cliques cluster COCOON color colorset competitive ratio complexity Computer Science consider contains convex cycle deﬁned Deﬁnition deletion denote deterministic diﬀerent dominating set dominating set problem edges eﬃcient enumeration exists ﬁnd ﬁnding ﬁrst ﬁxed ﬂow forecaster forest bound function G V,E given graph G greedy greedy algorithm Hamiltonian cycles haplotype Heidelberg input integer intersection graphs interval Lemma length linear LNCS lower bound maximal maximum minimal minimum nodes NP-complete NP-hard obtained optimal output paper parameter parameterized partition payoﬀ perfect phylogeny planar graphs polynomial proﬁt proof systems pure strategy randomized algorithm real numbers recoloring satisﬁes sequence set splitting problem spanning tree Springer Springer-Verlag Berlin Heidelberg stable matching strategy subgraph subset Theorem throughput treewidth variables vertex set weight white vertices