## Computing and Combinatorics: 9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25-28, 2003, ProceedingsThe papers in this volume were presented at the 9th Annual International C- puting and Combinatorics Conference (COCOON 2003), held July 25–28, 2003, in Big Sky, MT, USA. The topics cover most aspects of theoretical computer science and combinatorics related to computing. Submissionstotheconferencethisyearwereconductedelectronically.Atotal of 114 papers were submitted, of which 52 were accepted. The papers were evaluated by an international program committee consisting of Nina Amenta, Tetsuo Asano, Bernard Chazelle, Zhixiang Chen, Francis Chin, Kyung-Yong Chwa, Robert Cimikowski, Anne Condon, Michael Fellows, Anna Gal, Michael Hallett,DanielHuson,NaokiKatoh,D.T.Lee,BernardMoret,BrendanMumey, Gene Myers, Hung Quang Ngo, Takao Nishizeki, Cindy Phillips, David Sanko?, Denbigh Starkey, Jie Wang, Lusheng Wang, Tandy Warnow and Binhai Zhu. It is expected that most of the accepted papers will appear in a more complete form in scienti?c journals. The submitted papers were from Canada (6), China (7), Estonia (1), F- land (1), France (1), Germany (8), Israel (4), Italy (1), Japan (11), Korea (22), Kuwait (1), New Zealand (1), Singapore (2), Spain (1), Sweden (2), Switzerland (3), Taiwan (7), the UK (1) and the USA (34). Each paper was evaluated by at least three Program Committee members, assisted in some cases by subre- rees. In addition to selected papers, the conference also included three invited presentations by Jon Bentley, Dan Gus?eld and Joel Spencer. |

### What people are saying - Write a review

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

### Contents

Empirical Exploration of Perfect Phylogeny Haplotyping and Haplotypers | 5 |

Cylindrical Hierarchy for Deforming Necklaces | 20 |

Geometric Algorithms for Agglomerative Hierarchical Clustering | 30 |

Traveling Salesman Problem of Segments | 40 |

SubexponentialTime Algorithms for Maximum Independent Set and Related Problems on Box Graphs | 50 |

A Space Efficient Algorithm for Sequence Alignment with Inversions | 57 |

On the Similarity of Sets of Permutations and Its Applications to Genome Comparison | 68 |

On AllSubstrings Alignment Problems | 80 |

Complexity Theoretic Aspects of Some Cryptographic Functions | 294 |

Quantum Sampling for Balanced Allocations | 304 |

FaultHamiltonicity of Product Graph of Path and Cycle | 319 |

How to Obtain the Complete List of Caterpillars Extended Abstract | 329 |

Randomized Approximation of the Stable Marriage Problem | 339 |

Tetris is Hard Even to Approximate | 351 |

Approximate MST for UDG Locally | 364 |

Efficient Construction of LowWeight Bounded Degree Planar Spanner | 374 |

The SpeckerBlatter Theorem Revisited | 90 |

On the Divergence Bounded Computable Real Numbers | 102 |

Sparse ParityCheck Matrices over Finite Fields Extended Abstract | 112 |

On the Full and Bottleneck Full Steiner Tree Problems | 122 |

The Structure and Number of Global Roundings of a Graph | 130 |

On Even Triangulations of 2Connected Embedded Graphs | 139 |

Automatic Verification of Multiqueue Discrete Timed Automata | 159 |

List Total Colorings of SeriesParallel Graphs | 172 |

Finding Hidden Independent Sets in Interval Graphs | 182 |

Matroid Representation of Clique Complexes | 192 |

Positive and Negative Results | 202 |

The Complexity of Boolean Matrix Root Computation | 212 |

A Fast BitParallel Algorithm for Matching Extended Regular Expressions | 222 |

Group Mutual Exclusion Algorithms Based on Ticket Orders | 232 |

Distributed Algorithm for Better Approximation of the Maximum Matching | 242 |

Efficient Mappings for ParityDeclustered Data Layouts | 252 |

Approximate Rank Aggregation Preliminary Version | 262 |

Perturbation of the HyperLinked Environment | 272 |

Fast Construction of Generalized Suffix Trees over a Very Large Alphabet | 284 |

Isoperimetric Inequalities and the Width Parameters of Graphs | 385 |

Graph Coloring and the Immersion Order | 394 |

Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs | 404 |

Scheduling Broadcasts with Deadlines | 415 |

Improved Competitive Algorithms for Online Scheduling with Partial Job Values | 425 |

Majority Equilibrium for Public Facility Allocation Preliminary Version | 435 |

On Constrained Minimum Pseudotriangulations | 445 |

Pairwise Data Clustering and Applications | 455 |

Covering a Set of Points with a Minimum Number of Turns | 467 |

AreaEfficient OrderPreserving Planar StraightLine Drawings of Ordered Trees | 475 |

Bounds for Convex Crossing Numbers | 487 |

On Spectral Graph Drawing | 496 |

On a Conjecture on Wiener Indices in Combinatorial Chemistry | 509 |

Complexity and Approximability in the Presence of Noisy Data | 519 |

Fast and SpaceEfficient Location of Heavy or Dense Segments in RunLength Encoded Sequences Extended Abstract | 528 |

Genomic Distances under Deletions and Insertions | 537 |

Minimal Unsatisfiable Formulas with Bounded | 548 |

559 | |

### Other editions - View all

### Common terms and phrases

alignment approximation algorithm assignment Berlin Heidelberg 2003 binary bipartite bipartite graph circuit clique complex coloring Computer Science conserved intervals consider constant construct contains cycle deﬁne defined denote disjoint disk Double Digest edge eigenvectors elements function G-orientation gameboard genome given graph G haplotype Hence independent set input integer intersection interval graph inversion label sequence layered graph Lemma length Let G linear LNCS lower bound matching matrix matroids maximal maximum minimal minimum minimum spanning tree networks node NP-complete NP-hard obtained online algorithm optimal pair paper partition path permutations planar planar graph points polynomial problem Proc Proof pseudotriangulation queries queue random ratio real numbers satisfies segment series-parallel graph solution space spanner string structure subgraph subset substrings subtree suffix tree Tetris Theorem triangulation tuple vertex vertices Warnow weight Wiener Zhu Eds