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

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