𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tight comparison bounds for the string prefix-matching problem

✍ Scribed by Dany Breslauer; Livio Colussi; Laura Toniolo

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
621 KB
Volume
47
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the Comparison Complexity of the Stri
On the Comparison Complexity of the String Prefix-Matching Problem
✍ Dany Breslauer; Livio Colussi; Laura Toniolo πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 525 KB

In this paper we study the exact comparison complexity of the string prefixmatching problem in the deterministic sequential comparison model with equality tests. We derive almost tight lower and upper bounds on the number of symbol comparisons required in the worst case by on-line prefix-matching al

Tight Bounds for the Maximum Acyclic Sub
Tight Bounds for the Maximum Acyclic Subgraph Problem
✍ Bonnie Berger; Peter W Shor πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 209 KB

Given a directed graph G s V, A , the maximum acyclic subgraph problem is to Ž . find a maximum cardinality subset AЈ of the arcs such that GЈ s V, AЈ is acyclic. In this paper, we present polynomial-time and RNC algorithms which, when given Ž any graph G without two-cycles, find an acyclic subgraph

A New Lower Bound for the Football Pool
A New Lower Bound for the Football Pool Problem for Six Matches
✍ Patric R.J. Γ–stergΓ₯rd; Alfred Wassermann πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 89 KB

In the football pool problem one wants to minimize the cardinality of a ternary code, C F n 3 ; with covering radius one, and the size of a minimum code is denoted by s n : The smallest unsettled case is 634s 6 473: The lower bound is here improved to 65 in a coordinate-by-coordinate backtrack searc