Y. Kohayakawa, V. Rödl (auth.), Gaston H. Gonnet, Alfredo Viola (eds.)3540673067, 9783540673064
The 42 revised papers presented were carefully reviewed and selected from a total of 87 submissions from 26 countries. Also included are abstracts or full papers of several invited talks. The papers are organized in topical sections on random structures and algorithms, complexity, computational number theory and cryptography, algebraic algorithms, computability, automata and formal languages, and logic and programming theory.
Table of contents :
Front Matter….Pages –
Algorithmic Aspects of Regularity….Pages 1-17
Small Maximal Matchings in Random Graphs….Pages 18-27
Some Remarks on Sparsely Connected Isomorphism-Free Labeled Graphs….Pages 28-37
Analysis of Edge Deletion Processes on Faulty Random Regular Graphs….Pages 38-47
Equivalent Conditions for Regularity (Extended Abstract)….Pages 48-57
Cube Packing….Pages 58-67
Approximation Algorithms for Flexible Job Shop Problems….Pages 68-77
Emerging Behavior as Binary Search Trees Are Symmetrically Updated….Pages 78-87
The LCA Problem Revisited….Pages 88-94
Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays….Pages 95-104
Rank Inequalities for Packing Designs and Sparse Triple Systems….Pages 105-114
The Anti-Oberwolfach Solution: Pancyclic 2-Factorizations of Complete Graphs….Pages 115-122
Graph Structure of the Web: A Survey….Pages 123-125
Polynomial Time Recognition of Clique-Width ≤ 3 Graphs….Pages 126-134
On Dart-Free Perfectly Contractile Graphs Extended Abstract….Pages 135-144
Edge Colouring Reduced Indifference Graphs….Pages 145-153
Two Conjectures on the Chromatic Polynomial….Pages 154-162
Finding Skew Partitions Efficiently….Pages 163-172
On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract)….Pages 173-196
Almost k -Wise Independence and Hard Boolean Functions….Pages 197-206
Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function….Pages 207-216
Multi-parameter Minimum Spanning Trees….Pages 217-226
Linear Time Recognition of Optimal L-Restricted Prefix Codes….Pages 227-236
Uniform Multi-hop All-to-All Optical Routings in Rings….Pages 237-246
A Fully Dynamic Algorithm for Distributed Shortest Paths….Pages 247-257
Integer Factorization and Discrete Logarithms….Pages 258-258
Communication Complexity and Fourier Coefficients of the Diffie–Hellman Key….Pages 259-268
Quintic Reciprocity and Primality Test for Numbers of the Form $M~=~A5^{n} pm ~omega_{n}$ ….Pages 269-279
Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography….Pages 280-291
Average-Case Analysis of Rectangle Packings….Pages 292-297
Heights in Generalized Tries and PATRICIA Tries….Pages 298-307
On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths Extended Abstract….Pages 308-317
Subresultants Revisited….Pages 318-342
A Unifying Framework for the Analysis of a Class of Euclidean Algorithms….Pages 343-354
Worst-Case Complexity of the Optimal LLL Algorithm….Pages 355-366
Iteration Algebras Are Not Finitely Axiomatizable….Pages 367-376
Undecidable Problems in Unreliable Computations….Pages 377-386
Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups….Pages 387-396
Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers….Pages 397-406
Unambiguous Büchi Automata….Pages 407-416
Linear Time Language Recognition on Cellular Automata with Restricted Communication….Pages 417-426
From Semantics to Spatial Distribution….Pages 427-436
On the Expressivity and Complexity of Quantitative Branching-Time Temporal Logics….Pages 437-446
A Theory of Operational Equivalence for Interaction Nets….Pages 447-456
Run Statistics for Geometrically Distributed Random Variables….Pages 457-462
Generalized Covariances of Multi-dimensional Brownian Excursion Local Times….Pages 463-472
Combinatorics of Geometrically Distributed Random Variables: Length of Ascending Runs….Pages 473-482
Back Matter….Pages –
Reviews
There are no reviews yet.