Daniel Panario, Alfredo Viola (auth.), Cláudio L. Lucchesi, Arnaldo V. Moura (eds.)3540642757, 9783540642756
The 28 revised full papers presented together with five invited surveys were carefully selected from a total of 53 submissions based on 160 referees’ reports. The papers are organized in sections on algorithms and complexity; automata, transition systems and combinatorics on words; computational geometry and graph drawing; cryptography; graph theory and algorithms on graphs; packet routing; parallel algorithms; and pattern matching and browsing.
Table of contents :
Analysis of Rabin’s polynomial irreducibility test….Pages 1-10
A chip search problem on binary numbers….Pages 11-22
Uniform service systems with k servers….Pages 23-32
Faster non-linear parametric search with applications to optimization and dynamic geometry….Pages 33-41
Super-state automata and rational trees….Pages 42-52
An Eilenberg theorem for words on countable ordinals….Pages 53-64
Maximal groups in free Burnside semigroups….Pages 65-75
Positive varieties and infinite words….Pages 76-87
Unfolding parametric automata….Pages 88-101
Fundamental structures in Well-Structured infinite Transition Systems….Pages 102-118
Shape reconstruction with Delaunay complex….Pages 119-132
Bases for non-homogeneous polynomial C k splines on the sphere….Pages 133-140
The splitting number of the 4-cube….Pages 141-150
Short and smooth polygonal paths….Pages 151-162
Quantum cryptanalysis of hash and claw-free functions….Pages 163-169
Batch verification with applications to cryptography and checking….Pages 170-191
Strength of two Data Encryption Standard implementations under timing attacks….Pages 192-205
Spectral techniques in graph algorithms….Pages 206-215
Colouring graphs whose chromatic number is almost their maximum degree….Pages 216-225
Circuit covers in series-parallel mixed graphs….Pages 226-238
A linear time algorithm to recognize clustered planar graphs and its parallelization….Pages 239-248
A new characterization for parity graphs and a coloring problem with costs….Pages 249-260
On the clique operator….Pages 261-272
Dynamic packet routing on arrays with bounded buffers….Pages 273-281
On-Line matching routing on trees….Pages 282-291
Analyzing Glauber dynamics by comparison of Markov chains….Pages 292-304
The CREW PRAM complexity of modular inversion….Pages 305-315
Communication-efficient parallel multiway and approximate minimum cut computation….Pages 316-330
The geometry of browsing….Pages 331-340
Fast two-dimensional approximate pattern matching….Pages 341-351
Improved approximate pattern matching on hypertext….Pages 352-357
Solving equations in strings: On Makanin’s algorithm….Pages 358-373
Spelling approximate repeated or common motifs using a suffix tree….Pages 374-390
Reviews
There are no reviews yet.