Warnow / Zhu Computing and Combinatorics

9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25-28, 2003, Proceedings
Erscheinungsjahr 2003
ISBN: 978-3-540-45071-9
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 2697, 566 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Warnow, Tandy

Zhu, Binhai

Inhaltsverzeichnis

Invited Lecture.- LIAR!.- Experiments for Algorithm Engineering.- Empirical Exploration of Perfect Phylogeny Haplotyping and Haplotypers.- Computational Geometry I.- Cylindrical Hierarchy for Deforming Necklaces.- Geometric Algorithms for Agglomerative Hierarchical Clustering.- Traveling Salesman Problem of Segments.- Subexponential-Time Algorithms for Maximum Independent Set and Related Problems on Box Graphs.- Computational Biology I.- A Space Efficient Algorithm for Sequence Alignment with Inversions.- On the Similarity of Sets of Permutations and Its Applications to Genome Comparison.- On All-Substrings Alignment Problems.- Computational/Complexity Theory I.- The Specker-Blatter Theorem Revisited.- On the Divergence Bounded Computable Real Numbers.- Sparse Parity-Check Matrices over Finite Fields.- Graph Theory/Algorithms I.- On the Full and Bottleneck Full Steiner Tree Problems.- The Structure and Number of Global Roundings of a Graph.- On Even Triangulations of 2-Connected Embedded Graphs.- Automata/Petri Net Theory.- Petri Nets with Simple Circuits.- Automatic Verification of Multi-queue Discrete Timed Automata.- Graph Theory/Algorithms II.- List Total Colorings of Series-Parallel Graphs.- Finding Hidden Independent Sets in Interval Graphs.- Matroid Representation of Clique Complexes.- Complexity Theory II.- On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.- The Complexity of Boolean Matrix Root Computation.- A Fast Bit-Parallel Algorithm for Matching Extended Regular Expressions.- Distributed Computing.- Group Mutual Exclusion Algorithms Based on Ticket Orders.- Distributed Algorithm for Better Approximation of the Maximum Matching.- Efficient Mappings for Parity-Declustered Data Layouts.- Web-Based Computing.-Approximate Rank Aggregation.- Perturbation of the Hyper-Linked Environment.- Fast Construction of Generalized Suffix Trees over a Very Large Alphabet.- Complexity Theory III.- Complexity Theoretic Aspects of Some Cryptographic Functions.- Quantum Sampling for Balanced Allocations.- Graph Theory/Algorithms III.- Fault-Hamiltonicity of Product Graph of Path and Cycle.- How to Obtain the Complete List of Caterpillars.- Randomized Approximation of the Stable Marriage Problem.- Computational Geometry II.- Tetris is Hard, Even to Approximate.- Approximate MST for UDG Locally.- Efficient Construction of Low Weight Bounded Degree Planar Spanner.- Graph Theory/Algorithms IV.- Isoperimetric Inequalities and the Width Parameters of Graphs.- Graph Coloring and the Immersion Order.- Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs.- Scheduling.- Scheduling Broadcasts with Deadlines.- Improved Competitive Algorithms for Online Scheduling with Partial Job Values.- Majority Equilibrium for Public Facility Allocation.- Computational Geometry III.- On Constrained Minimum Pseudotriangulations.- Pairwise Data Clustering and Applications.- Covering a Set of Points with a Minimum Number of Turns.- Graph Drawing.- Area-Efficient Order-Preserving Planar Straight-Line Drawings of Ordered Trees.- Bounds for Convex Crossing Numbers.- On Spectral Graph Drawing.- Computational Biology II.- On a Conjecture on Wiener Indices in Combinatorial Chemistry.- Double Digest Revisited: Complexity and Approximability in the Presence of Noisy Data.- Fast and Space-Efficient Location of Heavy or Dense Segments in Run-Length Encoded Sequences.- Genomic Distances under Deletions and Insertions.- Fixed-Parameter Complexity Theory.- Minimal Unsatisfiable Formulas with Bounded Clause-Variable Difference are Fixed-Parameter Tractable.