We extend the algorithm of Galil and Giancarlo, which speeds up dynamic
programming in the case of concave cost functions, such that a compact
representation of *all* optimal solutions is computed.
Compared to the Galil-Giancarlo algorithms our time bound grows only by
a small constant factor.
With a compact representation, we develop efficient algorithms for the
solution of problems in molecular biology concerning the computation
of all optimal local alignments and all optimal subalignments in
genetic sequences.