Computing and Combinatorics: 9th Annual International Conference, Cocoon 2003, Big Sky, Mt, Usa, July 25-28, 2003 : Proceedings

by Cocoon 200 (2003 Big Sky, Mont.); Warnow, Tandy; Zhu, Binhai

• ISBN13: 9783540405344
• ISBN10: 3540405348
• Format: Paperback
• Copyright: 2003-08-01
• Publisher: Springer Verlag

Summary

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