Institut für Informatik V Arbeitsgruppe Prof. Blum

• Prof. Dr. N. Blum
• Dr. Claus Rick

• N. Blum,
Maximum Matching in General Graphs Without Explicit Consideration of Blossoms Revisited,


• N. Blum,
On LR(k)-parsers of polynomial size (pdf)
Implementation


• N. Blum,
Speeding up Dynamic Programming without Omitting any Optimal Solution and some Applications in Molecular Biology,
Journal of Algorithms 35 (2000), 129-168


• N. Blum,
On Parsing LL-Languages, TCS 267 (2001) 49-59


• N. Blum, R. Koch,
Greibach Normal Form Transformation, Revisited,
Information and Computation 150 (1999), 112-118


• N. Blum,
An O(n log n) implementation of the standard method for minimizing n-state finite automata,
IPL 57 (1996), 65-69


• N. Blum, H. Rochow
A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals,
IPL 51 (1994), 57-60


• N. Blum,
On the single-operation worst-case time complexity of the disjoint set union problem,
SIAM J. Comput. 15 (1986), 1021-1024


• N. Blum,
An Area-Maximum Edge Length Trade-off for VLSI Layout,
Information and Control 66 (1985), 45-52


• N. Blum,
An  lower bound on the monotone network complexity of the n-th degree convolution,
TCS 36 (1985), 59-69


• N. Blum, M. Seysen
Characterization of all Optimal Networks for a Simultaneous Computation of AND and NOR,
Acta Informatica 21 (1984), 171-181


• N. Blum,
A boolean funtion requiring 3n network size,
TCS 28 (1984), 337-345


• N. Blum,
More on the power of chain rules in context-free grammars,
TCS 27 (1983), 287-295


• N. Blum, K. Mehlhorn
On the average number of rebalancing operations in weight-balanced trees,
TCS 11 (1980), 303-320

Claus Rick,

Simple and Fast Linear Space Computation of Longest Common Subsequences,
Information Processing Letters, Vol. 75/6, 275 - 281,
Elsevier (2000)

Claus Rick,

Efficient Computation of All Longest Common Subsequences,
Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT 2000),
Lecture Notes in Computer Science, Vol. 1851, 407 - 418
Springer Verlag (2000)

Claus Rick, Hein Röhrig,

Deriving Non-Approximability Results by Reductions,
Chapter 8 (pp. 213 - 233) in: Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.),
Lectures on Proof Verification and Approximation Algorithms,
LNCS Tutorial, Vol. 1367,
Springer Verlag (1998)

Claus Rick,

A New Flexible Algorithm for the Longest Common Subsequence Problem,
Proceedings of the 6th Symposium on Combinatorial Pattern Matching (CPM'95),
Lecture Notes in Computer Science, Vol. 937, 340 - 351,
Springer Verlag (1995)
Also in Nordic Journal of Computing (NJC), Vol. 2, No. 4, Winter 1995, 444 - 461.

Claus Rick,

New Algorithms for the Longest Common Subsequence Problem,
Research Report No. 85123-CS, University of Bonn, October 1994

[}