Beautiful Algorithms and
Structures
(by Yefim Dinitz, in preparation)
The goal of the site
Beautiful
discrete algorithms and structures are my permanent love. The fact that they are
old does not decrease my feeling. Some of them were discovered by me or by close
colleagues. Hence, I feel well the ideas that they are based on, and probably
have an ability to present them deeply to the wide audience. This is the main
goal of the site.
The site
concentrates on ideas, not on facts. Moreover, when possible, it shows also
origins of those ideas. Such a meta-point of view shows how new ideas were
revealed. Hence, it may be instructive to students wishing be researchers, and
enjoyable to mature researchers. It may become a complement to the industrial
approach to research, widely spread nowadays.
At the
site pages, the basic hints are provided to each topic, followed by references
to published, detailed texts. The best way for the reader, recommended to those
who likes challenges, is trying to restore the solution basing on the provided
hints. Applying to the published text may be supplementary: either for refining
the problem definition, or when a few attempts were not sufficient for
overcoming a difficulty, or for comparing the solution found with the published
one, or for finding additional statements completing the topic. In any case, it
is recommended trying to prove each statement from the published text before
reading its proof. This is the way that I enjoyed when studying, at the early
era of Computer Science.
Following
is the contents of the site, with hyperlinks to its pages. The presentation
order mostly follows the chronology of my research life.
1.
Historical
introduction: Early Moscow School of Programming.
Running time saving by information re-using, amortized counting, and look-up
tables (1947-1968)
2.
AVL-tree, a basic dynamic data structure structure for maintaining sorting, by
Adelson-Velsky and Landis (1962)
4.
Basic Assignment problem solution as a
representative primal-dual algorithm. Time-saving for gradually changing sub-matrices
(1969)
5.
Ford-Fulkerson maximal flow algorithm, as a
representative non-greedy algorithm (1962)
6.
Dinitz's (Dinic's) maximal flow algorithm, based
Layered Network dynamic data structure (1970)
7.
Time bounds of Dinitz's
algorithm by Karzanov, for Maximal Matching finding. (=Hopcroft-Karp
algorithm) (1971)
8.
Polynomial scaling algorithm for
Transportation Problem (a variant of the min-cost max flow problem) (1973)
9.
Cherkassky's Maximum Multi-Terminal
Flow algorithm, in an undirected graph (1975)
10.
Podderjugin's algorithm for finding a minimum cut in an (undirected)
graph. A representative amortized counting for a running time
bound, one of the first published ones (1971)
11.
The book
"Network flow Algorithms" (in Russian) (1975)
12.
Cactus Tree structure of the minimum cuts, in an (undirected) graph (1976)
13.
The structure of 1-, 2-, 3-, and 4-cuts, in an (undirected) graph, and
its maintenance following edge additions (1992, 1994,
2000)
14.
. . .
15.
Bit Complexity of distributed symmetry breaking (1999)
16.
A Hanoi Towers problem with relaxed constraints (2006)
17.
Time-scheduling with AND/OR precedence constraints (1990, 2001)
Comments aimed improving the site presentation (including
English) are welcome.