## Computing and Combinatorics: 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002 Proceedings, Volume 8The abstract and papers in this volume were presented at the Eighth Annual International Computing and Combinatorics Conference (COCOON 2002), held on August 15-17 in Singapore. The topics cover various aspects of theoretical computer science and combinatorics related to computing. Submissionstotheconferencethisyearwereconductedelectronically. The60 papers were selected for presentation from a total of 106 submitted papers from Australia (6), Canada (3), China (6), Germany (9), India (5), Japan (11), Korea (10), Singapore (5), Taiwan (8), United States (29), and 11 other countries and regions (14). The papers were evaluated by an international program comm- tee consisting of Mikhail Atallah, Jik Chang, Tim Ting Chen, Siu-Wing Cheng, Omer Egecioglu, Fan Chung Graham, Susanne Hambrusch, Sorin Istrail, S- path Kannan, Ming-Yang Kao, Shlomo Moran, Koji Nakano, Takao Nishizeki, Steve Olariu, Gheorghe Paun, Pandu Rangan, Sartaj Sahni, Arto Salomaa, Igor Shparlinski, Janos Simon, Paul Spirakis, Chung Piaw Teo, Jan van Leeuwen, Paul Vitanyi, Peter Widmayer, and Hsu-Chun Yen. It is expected that most of the accepted papers will appear in a more complete form in scienti'c journals. In addition to the contributed papers, three invited lectures were presented by Eugene W. Myers, Sartaj Sahni, and Arto Salomaa. We wish to thank all who have made this meeting possible: the authors for submitting papers, the program committee members and external referees (listed in the proceedings) for their excellent work, and the three invited spe- ers. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

The Assembly of the Human and Mouse Genomes | 1 |

Data Structures for OneDimensional Packet Classification Using MostSpecificRule Matching | 2 |

DNA Complementarity and Paradigms of Computing | 3 |

On Higher ArthurMerlin Classes | 18 |

2+fnSAT and Its Properties | 28 |

On the Minimal Polynomial of a Matrix | 37 |

Computable Real Functions of Bounded Variation and Semicomputable Real Numbers Extended Abstract | 47 |

Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees | 57 |

SelfAssembling Finite Automata | 310 |

Repetition Complexity of Words | 320 |

Using PageRank to Characterize Web Structure | 330 |

On Randomized Broadcasting and Gossiping in Radio Networks | 340 |

Fast and Dependable Communication in Hyperrings | 350 |

The OnLine Heilbronns Triangle Problem in Three and Four Dimensions | 360 |

Algorithms for Normal Curves and Surfaces | 370 |

Terrain Polygon Decomposition with Application to Layered Manufacturing | 381 |

Coloring Algorithms on Subcubic Graphs | 67 |

Efficient Algorithms for the Hamiltonian Problem on DistanceHereditary Graphs | 77 |

Extending the Accommodating Function | 87 |

Inverse Parametric Sequence Alignment | 97 |

The Full Steiner Tree Problem in Phylogeny | 107 |

Inferring a Union of Halfspaces from Examples | 117 |

Dictionary LookUp within Small Edit Distance | 127 |

Polynomial Interpolation of the Elliptic Curve and XTR Discrete Logarithm | 137 |

Coorthogonal Codes Extended Abstract | 144 |

Efficient PowerSum Systolic Architectures for PublicKey Cryptosystems in GF2m | 153 |

A Combinatorial Approach to Anonymous Membership Broadcast | 162 |

Solving Constraint Satisfaction Problems with DNA Computing | 171 |

New Architecture and Algorithms for Degradable VLSIWSI Arrays | 181 |

A Fast Tool to Identify Groups of Similar Programs | 191 |

Broadcasting in Generalized de Bruijn Digraphs Extended Abstract | 200 |

On the Connected Domination Number of Random Regular Graphs | 210 |

On the Number of Minimum Cuts in a Graph | 220 |

On Crossing Numbers of 5Regular Graphs | 230 |

Maximum Flows and Critical Vertices in ANDOR Graphs Extended Abstract | 238 |

New EnergyEfficient Permutation Routing Protocol for SingleHop Radio Networks | 249 |

Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model | 259 |

Time and Energy Optimal List Ranking Algorithms on the kChannel Broadcast Communication Model | 269 |

EnergyEfficient Size Approximation of Radio Networks with No Collision Detection | 279 |

Tissue P Systems | 290 |

Transducers with Set Output | 300 |

Supertrees by Flipping | 391 |

A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays | 401 |

Sharpening Occams Razor Extended Abstract | 411 |

Approximating 3D Points with Cylindrical Segments | 420 |

Algorithms for the Multicolorings of Partial kTrees | 430 |

A FaultTolerant Merge Sorting Algorithm | 440 |

2Compromise Usability in 1Dimensional Statistical Databases | 448 |

An Experimental Study and Comparison of Topological Peeling and Topological Walk | 456 |

OnLine Maximizing the Number of Items Packed in VariableSized Bins | 467 |

OnLine GridPacking with a Single Active Grid | 476 |

Bend Minimization in Orthogonal Drawings Using Integer Programming | 484 |

The Conditional Location of a Median Path | 494 |

New Results on the kTruck Problem | 504 |

Theory of EqualFlows in Networks | 514 |

Minimum BackWalkFree Latency Problem Extended Abstract | 525 |

Counting Satisfying Assignments in 2SAT and 3SAT | 535 |

On the Maximum Number of Irreducible Coverings of an nVertex Graph by n3 Cliques | 544 |

On Reachability in Graphs with Bounded Independence Number | 554 |

On Parameterized Enumeration | 564 |

Probabilistic Reversible Automata and Quantum Automata | 574 |

Quantum versus Deterministic Counter Automata | 584 |

Quantum DNF Learnability Revisited | 595 |

605 | |

### Other editions - View all

### Common terms and phrases

alignment AND/OR graph assume automata automaton Berlin Heidelberg 2002 binary broadcasting cell color competitive ratio complexity Computer Science connected consider construct contains cycle deﬁne defined Deﬁnition denote deterministic digraph distance-hereditary graphs DNA computing edge equations exists finite function given graph G Hamming distance Hence input integer intersection language Lemma length linear LNCS logn lower bound matrix minimal minimal polynomial minimum cuts multiset node NP-complete NP-hard O.H. Ibarra obtained off-line algorithm optimal output packets packing PageRank pair parameter path planar planar graph points polynomial problem programs Proof protocol quantum random randomized algorithm satisﬁes segment sequence slots solution solved Springer-Verlag Berlin Heidelberg station Steiner tree step strands string subgraph subset suffix array Theorem topological peeling topological walk transducer undirected graph upper bound variables vertex vertices word Zhang Eds