Computing and Combinatorics: 9th Annual International Conference, COCOON 2003 Big Sky, MT, USA, July 25–28, 2003 Proceedings

Joel Spencer (auth.), Tandy Warnow, Binhai Zhu (eds.)3540405348, 9783540405344

This book constitutes the refereed proceedings of the 9th Annual International Computing and Combinatorics Conference, COCOON 2003, held in Big Sky, MT, USA in July 2003.

The 52 revised full papers presented together with 3 invited contributions were carefully reviewed and selected from 114 submissions. The papers are organized in topical sections on computational geometry, computational biology, computability and complexity theory, graph theory and graph algorithms, automata and Petri net theory, distributed computing, Web-based computing, scheduling, graph drawing, and fixed-parameter complexity theory.

---

Table of contents :
LIAR!….Pages 1-2
Experiments for Algorithm Engineering….Pages 3-4
Empirical Exploration of Perfect Phylogeny Haplotyping and Haplotypers….Pages 5-19
Cylindrical Hierarchy for Deforming Necklaces….Pages 20-29
Geometric Algorithms for Agglomerative Hierarchical Clustering….Pages 30-39
Traveling Salesman Problem of Segments….Pages 40-49
Subexponential-Time Algorithms for Maximum Independent Set and Related Problems on Box Graphs….Pages 50-56
A Space Efficient Algorithm for Sequence Alignment with Inversions….Pages 57-67
On the Similarity of Sets of Permutations and Its Applications to Genome Comparison….Pages 68-79
On All-Substrings Alignment Problems….Pages 80-89
The Specker-Blatter Theorem Revisited….Pages 90-101
On the Divergence Bounded Computable Real Numbers….Pages 102-111
Sparse Parity-Check Matrices over Finite Fields….Pages 112-121
On the Full and Bottleneck Full Steiner Tree Problems….Pages 122-129
The Structure and Number of Global Roundings of a Graph….Pages 130-138
On Even Triangulations of 2-Connected Embedded Graphs….Pages 139-148
Petri Nets with Simple Circuits….Pages 149-158
Automatic Verification of Multi-queue Discrete Timed Automata….Pages 159-171
List Total Colorings of Series-Parallel Graphs….Pages 172-181
Finding Hidden Independent Sets in Interval Graphs….Pages 182-191
Matroid Representation of Clique Complexes….Pages 192-201
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results….Pages 202-211
The Complexity of Boolean Matrix Root Computation….Pages 212-221
A Fast Bit-Parallel Algorithm for Matching Extended Regular Expressions….Pages 222-231
Group Mutual Exclusion Algorithms Based on Ticket Orders….Pages 232-241
Distributed Algorithm for Better Approximation of the Maximum Matching….Pages 242-251
Efficient Mappings for Parity-Declustered Data Layouts….Pages 252-261
Approximate Rank Aggregation….Pages 262-271
Perturbation of the Hyper-Linked Environment….Pages 272-283
Fast Construction of Generalized Suffix Trees over a Very Large Alphabet….Pages 284-293
Complexity Theoretic Aspects of Some Cryptographic Functions….Pages 294-303
Quantum Sampling for Balanced Allocations….Pages 304-318
Fault-Hamiltonicity of Product Graph of Path and Cycle….Pages 319-328
How to Obtain the Complete List of Caterpillars….Pages 329-338
Randomized Approximation of the Stable Marriage Problem….Pages 339-350
Tetris is Hard, Even to Approximate….Pages 351-363
Approximate MST for UDG Locally….Pages 364-373
Efficient Construction of Low Weight Bounded Degree Planar Spanner….Pages 374-384
Isoperimetric Inequalities and the Width Parameters of Graphs….Pages 385-393
Graph Coloring and the Immersion Order….Pages 394-403
Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs….Pages 404-414
Scheduling Broadcasts with Deadlines….Pages 415-424
Improved Competitive Algorithms for Online Scheduling with Partial Job Values….Pages 425-434
Majority Equilibrium for Public Facility Allocation….Pages 435-444
On Constrained Minimum Pseudotriangulations….Pages 445-454
Pairwise Data Clustering and Applications….Pages 455-466
Covering a Set of Points with a Minimum Number of Turns….Pages 467-474
Area-Efficient Order-Preserving Planar Straight-Line Drawings of Ordered Trees….Pages 475-486
Bounds for Convex Crossing Numbers….Pages 487-495
On Spectral Graph Drawing….Pages 496-508
On a Conjecture on Wiener Indices in Combinatorial Chemistry….Pages 509-518
Double Digest Revisited: Complexity and Approximability in the Presence of Noisy Data….Pages 519-527
Fast and Space-Efficient Location of Heavy or Dense Segments in Run-Length Encoded Sequences….Pages 528-536
Genomic Distances under Deletions and Insertions….Pages 537-547
Minimal Unsatisfiable Formulas with Bounded Clause-Variable Difference are Fixed-Parameter Tractable….Pages 548-558