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

Front Cover
Springer Science & Business Media, Jul 9, 2003 - Computers - 560 pages
The 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
Author Index
559
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information