Jennifer Chayes (auth.), Sergio Rajsbaum (eds.)3540434003, 9783540434009
The 44 revised full papers presented together with a tutorial and 7 abstracts of invited contributions were carefully reviewed and selected from a total of 104 submissions. The papers presented are devoted to a broad range of topics from theoretical computer science and mathematical foundations, with a certain focus on algorithmics and computations related to discrete structures.
Table of contents :
Phase Transitions in Computer Science….Pages 1-1
The Internet, the Web, and Algorithms….Pages 2-2
Erdős Magic….Pages 3-3
Open Problems in Computational Geometry….Pages 4-11
Quantum Algorithms….Pages 12-13
Testing and Checking of Finite State Systems….Pages 14-14
From Algorithms to Cryptography Tutorial….Pages 15-15
Dihomotopy as a Tool in State Space Analysis Tutorial….Pages 16-37
Algorithms for Local Alignment with Length Constraints * ….Pages 38-51
An Algorithm That Builds a Set of Strings Given Its Overlap Graph….Pages 52-63
Conversion between Two Multiplicatively Dependent Linear Numeration Systems….Pages 64-75
Star Height of Reversible Languages and Universal Automata….Pages 76-90
Weakly Iterated Block Products of Finite Monoids….Pages 91-104
The Hidden Number Problem in Extension Fields and Its Applications….Pages 105-117
The Generalized Weil Pairing and the Discrete Logarithm Problem on Elliptic Curves….Pages 118-130
Random Partitions with Non Negative rth Differences….Pages 131-140
Beta-Expansions for Cubic Pisot Numbers….Pages 141-152
Facility Location Constrained to a Polygonal Domain….Pages 153-164
A Deterministic Polynomial Time Algorithm for Heilbronn’s Problem in Dimension Three….Pages 165-180
A Metric Index for Approximate String Matching….Pages 181-195
On Maximal Suffices and Constant-Space Linear-Time Versions of KMP Algorithm….Pages 196-208
On the Power of BFS to Determine a Graphs Diameter….Pages 209-223
k -pseudosnakes in Large Grids….Pages 224-235
L (2, 1)-Coloring Matrogenic Graphs….Pages 236-247
Pipeline Transportation of Petroleum Products with No Due Dates….Pages 248-262
Ancestor Problems on Pure Pointer Machines….Pages 263-277
Searching in Random Partially Ordered Sets….Pages 278-292
Packing Arrays….Pages 293-305
Generalized Shannon Code Minimizes the Maximal Redundancy….Pages 306-318
An Improved Algorithm for Sequence Comparison with Block Reversals….Pages 319-325
Pattern Matching and Membership for Hierarchical Message Sequence Charts….Pages 326-340
Improved Exact Algorithms for Max-Sat….Pages 341-355
Characterising Strong Normalisation for Explicit Substitutions….Pages 356-370
Parameters in Pure Type Systems….Pages 371-385
Category, Measure, Inductive Inference: A Triality Theorem and Its Applications….Pages 386-399
Verification of Embedded Reactive Fiffo Systems….Pages 400-414
Electronic Jury Voting Protocols….Pages 415-429
Square Roots Modulo p ….Pages 430-434
Finding Most Sustainable Paths in Networks with Time-Dependent Edge Reliabilities….Pages 435-450
Signals for Cellular Automata in Dimension 2 or Higher….Pages 451-464
Holographic Trees….Pages 465-478
On the Spanning Ratio of Gabriel Graphs and β-skeletons….Pages 479-493
In-Place Planar Convex Hull Algorithms….Pages 494-507
The Level Ancestor Problem Simplified….Pages 508-515
Flow Metrics….Pages 516-527
On Logical Descriptions of Regular Languages….Pages 528-538
Computing Boolean Functions from Multiple Faulty Copies of Input Bits….Pages 539-553
Inapproximability Results on Stable Marriage Problems….Pages 554-568
Tight Bounds for Online Class-Constrained Packing….Pages 569-583
On-line Algorithms for Edge-Disjoint Paths in Trees of Rings….Pages 584-597
Massive Quasi-Clique Detection….Pages 598-612
Improved Tree Decomposition Based Algorithms for Domination-like Problems….Pages 613-627
Reviews
There are no reviews yet.