Computing and Combinatorics: 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings

Front Cover
Guohui Lin
Springer Science & Business Media, Jun 29, 2007 - Computers - 570 pages
The 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
Author Index
568
Copyright

Other editions - View all

Common terms and phrases