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

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