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

Front Cover
Springer Science & Business Media, Jul 31, 2002 - Computers - 606 pages
The 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
Author Index
605
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information