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

Front Matter....Pages -
The Combinatorics of Sequencing the Corn Genome....Pages 1-1
Online Frequency Assignment in Wireless Communication Networks....Pages 2-2
Information Distance from a Question to an Answer....Pages 3-3
A New Field Splitting Algorithm for Intensity-Modulated Radiation Therapy....Pages 4-15
A New Recombination Lower Bound and the Minimum Perfect Phylogenetic Forest Problem....Pages 16-26
Seed-Based Exclusion Method for Non-coding RNA Gene Search....Pages 27-39
A New Quartet Approach for Reconstructing Phylogenetic Trees: Quartet Joining Method....Pages 40-50
Integer Programming Formulations and Computations Solving Phylogenetic and Population Genetic Problems with Missing or Genotypic Data....Pages 51-64
Improved Exact Algorithms for Counting 3- and 4-Colorings....Pages 65-74
Connected Coloring Completion for General Graphs: Algorithms and Complexity....Pages 75-85
Quadratic Kernelization for Convex Recoloring of Trees....Pages 86-96
On the Number of Cycles in Planar Graphs....Pages 97-107
An Improved Exact Algorithm for Cubic Graph TSP....Pages 108-117
Geometric Intersection Graphs: Do Short Cycles Help?....Pages 118-128
Dimension, Halfspaces, and the Density of Hard Sets....Pages 129-139
Isolation Concepts for Enumerating Dense Subgraphs....Pages 140-150
Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in O ( n 4 ) Time....Pages 151-164
Counting Minimum Weighted Dominating Sets....Pages 165-175
Online Interval Scheduling: Randomized and Multiprocessor Cases....Pages 176-186
Scheduling Selfish Tasks: About the Performance of Truthful Algorithms....Pages 187-197
Volume Computation Using a Direct Monte Carlo Method....Pages 198-209
Improved Throughput Bounds for Interference-Aware Routing in Wireless Networks....Pages 210-221
Generating Minimal k-Vertex Connected Spanning Subgraphs....Pages 222-231
Finding Many Optimal Paths Without Growing Any Optimal Path Trees....Pages 232-242
Enumerating Constrained Non-crossing Geometric Spanning Trees....Pages 243-253
Colored Simultaneous Geometric Embeddings....Pages 254-263
Properties of Symmetric Incentive Compatible Auctions....Pages 264-273
Finding Equilibria in Games of No Chance....Pages 274-284
Efficient Testing of Forecasts....Pages 285-295
When Does Greedy Learning of Relevant Attributes Succeed?....Pages 296-306
The Informational Content of Canonical Disjoint NP-Pairs....Pages 307-317
On the Representations of NC and Log-Space Real Numbers....Pages 318-326
Bounded Computable Enumerability and Hierarchy of Computably Enumerable Reals....Pages 327-337
Streaming Algorithms Measured in Terms of the Computed Quantity....Pages 338-348
A Randomized Approximation Algorithm for Parameterized 3-D Matching Counting Problem....Pages 349-359
Optimal Offline Extraction of Irredundant Motif Bases....Pages 360-371
Linear Algorithm for Broadcasting in Unicyclic Graphs....Pages 372-382
An Improved Algorithm for Online Unit Clustering....Pages 383-393
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs....Pages 394-405
Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions....Pages 406-416
On the Hardness of Optimization in Power Law Graphs....Pages 417-427
Can a Graph Have Distinct Regular Partitions?....Pages 428-438
Algorithms for Core Stability, Core Largeness, Exactness, and Extendability of Flow Games....Pages 439-447
Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates....Pages 448-458
On the Complexity of Finding an Unknown Cut Via Vertex Queries....Pages 459-469
“Resistant” Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas....Pages 470-481
An Improved Algorithm for Tree Edit Distance Incorporating Structural Linearity....Pages 482-492
Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats....Pages 493-503
Priority Algorithms for the Subset-Sum Problem....Pages 504-514
Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families....Pages 515-525
A 1-Local 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs....Pages 526-536
Improved Algorithms for Weighted and Unweighted Set Splitting Problems....Pages 537-547
An $\frac{8}{5}$ -Approximation Algorithm for a Hard Variant of Stable Marriage....Pages 548-558
Approximation Algorithms for the Black and White Traveling Salesman Problem....Pages 559-567
Back Matter....Pages -