Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002 Proceedings

Gene Myers Ph.D (auth.), Oscar H. Ibarra, Louxin Zhang (eds.)354043996X, 9783540439967

This book constitutes the refereed proceedings of the 8th Annual International Computing and Combinatorics Conference, COCOON 2002, held in Singapore in August 2002.
The 60 revised full papers presented together with three invited contributions were carefully reviewed and selected from 106 submissions. The papers are organized in topical sections on complexity theory, discrete algorithms, computational biology and learning theory, radio networks, automata and formal languages, Internet networks, computational geometry, combinatorial optimization, and quantum computing.

---

Table of contents :
The Assembly of the Human and Mouse Genomes….Pages 1-1
Data Structures for One-Dimensional Packet Classification Using Most-Specific-Rule Matching….Pages 2-2
DNA Complementarity and Paradigms of Computing….Pages 3-17
On Higher Arthur-Merlin Classes….Pages 18-27
(2 + f ( n ))-SAT and Its Properties….Pages 28-36
On the Minimal Polynomial of a Matrix….Pages 37-46
Computable Real Functions of Bounded Variation and Semi-computable Real Numbers….Pages 47-56
Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees….Pages 57-66
Coloring Algorithms on Subcubic Graphs….Pages 67-76
Efficient Algorithms for the Hamiltonian Problem on Distance-Hereditary Graphs….Pages 77-86
Extending the Accommodating Function….Pages 87-96
Inverse Parametric Sequence Alignment….Pages 97-106
The Full Steiner Tree Problem in Phylogeny….Pages 107-116
Inferring a Union of Halfspaces from Examples….Pages 117-126
Dictionary Look-Up within Small Edit Distance….Pages 127-136
Polynomial Interpolation of the Elliptic Curve and XTR Discrete Logarithm….Pages 137-143
Co-orthogonal Codes….Pages 144-152
Efficient Power-Sum Systolic Architectures for Public-Key Cryptosystems in GF(2 m )….Pages 153-161
A Combinatorial Approach to Anonymous Membership Broadcast….Pages 162-170
Solving Constraint Satisfaction Problems with DNA Computing….Pages 171-180
New Architecture and Algorithms for Degradable VLSI/WSI Arrays….Pages 181-190
Cluster: A Fast Tool to Identify Groups of Similar Programs….Pages 191-199
Broadcasting in Generalized de Bruijn Digraphs….Pages 200-209
On the Connected Domination Number of Random Regular Graphs….Pages 210-219
On the Number of Minimum Cuts in a Graph….Pages 220-229
On Crossing Numbers of 5-Regular Graphs….Pages 230-237
Maximum Flows and Critical Vertices in AND/OR Graphs….Pages 238-248
New Energy-Efficient Permutation Routing Protocol for Single-Hop Radio Networks….Pages 249-258
Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model….Pages 259-268
Time and Energy Optimal List Ranking Algorithms on the k -Channel Broadcast Communication Model….Pages 269-278
Energy-Efficient Size Approximation of Radio Networks with No Collision Detection….Pages 279-289
A New Class of Symbolic Abstract Neural Nets: Tissue P Systems….Pages 290-299
Transducers with Set Output….Pages 300-309
Self-assembling Finite Automata….Pages 310-319
Repetition Complexity of Words….Pages 320-329
Using PageRank to Characterize Web Structure….Pages 330-339
On Randomized Broadcasting and Gossiping in Radio Networks….Pages 340-349
Fast and Dependable Communication in Hyper-rings….Pages 350-359
The On-Line Heilbronn’s Triangle Problem in Three and Four Dimensions….Pages 360-369
Algorithms for Normal Curves and Surfaces….Pages 370-380
Terrain Polygon Decomposition, with Application to Layered Manufacturing….Pages 381-390
Supertrees by Flipping….Pages 391-400
A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays….Pages 401-410
Sharpening Occam’s Razor….Pages 411-419
Approximating 3D Points with Cylindrical Segments….Pages 420-429
Algorithms for the Multicolorings of Partial k -Trees….Pages 430-439
A Fault-Tolerant Merge Sorting Algorithm….Pages 440-447
2-Compromise Usability in 1-Dimensional Statistical Databases….Pages 448-455
An Experimental Study and Comparison of Topological Peeling and Topological Walk….Pages 456-466
On-Line Maximizing the Number of Items Packed in Variable-Sized Bins….Pages 467-475
On-Line Grid-Packing with a Single Active Grid….Pages 476-483
Bend Minimization in Orthogonal Drawings Using Integer Programming….Pages 484-493
The Conditional Location of a Median Path….Pages 494-503
New Results on the k -Truck Problem….Pages 504-513
Theory of Equal-Flows in Networks….Pages 514-524
Minimum Back-Walk-Free Latency Problem….Pages 525-534
Counting Satisfying Assignments in 2-SAT and 3-SAT….Pages 535-543
On the Maximum Number of Irreducible Coverings of an n -Vertex Graph by n — 3 Cliques….Pages 544-553
On Reachability in Graphs with Bounded Independence Number….Pages 554-563
On Parameterized Enumeration….Pages 564-573
Probabilistic Reversible Automata and Quantum Automata….Pages 574-583
Quantum versus Deterministic Counter Automata….Pages 584-594
Quantum DNF Learnability Revisited….Pages 595-604