The Origins of

Minimal Spanning Tree Algorithms –

Borůvka and Jarník

Jaroslav Nešetřil and Helena Nešetřilová

2010 Mathematics Subject Classification: 01-00, 05-03, 90-03, 01A60, 01A70, 05C85, 05C90, 68R15 Keywords and Phrases: Minimal spanning tree, Borůvka, Jarník, history of computing

1 Introduction

In this paper we discuss the early history of Minimum Spanning Tree problem and its solution. The MST problem is a corner stone of combinatorial optimization and its history is rich. It has been described in detail in several places, for example, one can mention [22] which gives a general overview of the history of combinatorial optimization; historically exhaustive paper [9]; another historical paper which contains the first commented translation of the original papers of Borůvka into English [19]; the paper [13] which deals with early papers by Jarník; and papers [18] and particularly [16], which cover the later rich development from contemporary perspective. Here we complement this by concentraiting on the very early beginning of this development before 1930. It is accepted by now that two papers [1], [2] by Borůvka in 1926 and Jarník [11] in 1930 are the first papers providing a solution to Minimum Spanning Tree problem. We document this together with remarks illustrating the milieu of this discovery and personalities of both authors (and Borůvka in particular).

2 Paper No. 1

Otakar Borůvka published three papers in 1926, two of which are our optimization papers: the paper [2] appeared in a local mathematical journal in Brno and the other in an engineering magazine Elektrotechnický obzor [1] (Electrotechnical Overview). The paper [2] has 22 pages and it was repeatedly described as unnecessary complicated. Paper [1] has a single page and it is little known (for example, it is not listed among his scientific works neither in [20] nor [4]).

However we believe that this is the key paper. It demonstrates how clearly Borůvka understood the problem and its algorithmic solution. The paper is very short and thus we can include the English translation in full (the original paper was written in Czech).

2.1 Translation of “Příspěvek k řešení otázky ekonomické stavby elektrovodných sítí”

Dr. Otakar Borůvka

A CONTRIBUTION TO THE SOLUTION OF A PROBLEM

OF ECONOMIC CONSTRUCTION OF ELECTRIC POWER-LINE NETWORKS

In my paper “On a certain minimal problem”(to appear in Práce moravské přírodovědecké společnosti) I proved a general theorem, which, as a special case, solves the following problem: There are n points given in the plane (in the space) whose mutual distances are all different. We wish to join them by a net such that 1. Any two points are joined either directly or by means of some points, 2. The total length of the net would be the shortest possible. It is evident that a solution of this problem could have some importace in electricity power-line network design; hence I present the solution briefly using an example. The reader with a deeper interest in the subject is referred to the above quoted paper. I shall give a solution of the problem in the case of 40 points given in Fig. 1. I shall join each of the given points with the nearest neighbor. Thus, for example, point 1 with point 2, point 2 with point 3, point 3 with point 4 (point 4 with point 3), point 5 with point 2, point 6 with point 5, point 7 with point 6, point 8 with point 9, (point 9 with point 8), etc. I shall obtain a sequence of polygonal strokes 1, 2, …, 13 (Fig. 2). I shall join each of these strokes with the nearest stroke in the shortest possible way. Thus, for example, stroke 1 with stroke 2, (stroke 2 with stroke 1), stroke 3 with stroke 4, (stroke 4 with stroke 3), etc. I shall obtain a sequence of polygonal strokes 1, 2, …, 4 (Fig. 3) I shall join each of these strokes in the shortest way with the nearest stroke. Thus stroke 1 with stroke 3, stroke 2 with stroke 3 (stroke 3 with stroke 1), stroke 4 with stroke 1. I shall finally obtain a single polygonal stroke (Fig. 4), which solves the given problem.

2.2 Remarks on “Příspěvěk k řešení problému ekonomické konstrukce elektrovodných sítí”

The numbering of Figures is clear from a copy of the original article which we include below.

Figure 1: Borůvka’s short paper [1]

This paper is written in a nearly contemporary style. An example given (40 cities) is derived from the original motivation of Borůvka’s research which was a problem related to the electrification of south-west Moravia. (See Section 6 about further details of Borůvka’s motivation.) Paper [2] contains yet another example with 74 cities. The electrification of South-Moravia was an actual topic in the early 20th century and it was very close to the editors of the Elektrotechnický obzor. (Note also that South-Moravia is one of the developed and cultured parts of Europe. It is and has been for centuries fully industrialized and yet a wine growing, rich and beautiful country. The core part of it is now protected by UNESCO.)

As a good analyst Borůvka viewed the assumption on distinct distances as unimportant. Once he told us: “if we measure distances, we can assume that they are all different. Whether distance from Brno to Břeclav is 50 km or 50 km and 1 cm is a matter of conjecture” [5].

We tried to keep the view of the original article. A careful reader can observe that the last figure (Fig. 4) in Borůvka’s paper [1] is reversed. This was noted already by Borůvka in 1926 as seen from our depicted copy which he mailed to Prof. Bydžovský).

Of course, the Elektrotechnický obzor is not a mathematical journal. Yet, this was a proper place to publish the result. The magazine was founded in 1910 (and it has been published by that name until 1991 when it merged with other journals under the name Elektro). It was the first Czech journal focussed on electricity. It was founded by Vladimír List, engineer and professor in Brno (who served as president of the Czech Technical University in Brno and, among other things, was Chairman of the International standards organization ISA). He advocated the systematic electrification of Moravia and convinced authorities to build public high voltage trasmission lines. Borůvka began his studies at the the Technical University in Brno.

3 Contemporary setting

Before discussing the paper [2] let us include, for comparision, the well known contemporary formulations of the Minimum Spanning Tree problem, Borůvka’s algorithm and the proof, see, e.g., [23].

Problem (MST). Let G = (V, E) be an undirected connected graph with n vertices and m edges. For each edge e let w(e) be a real weight of the edge e and let us assume that w(e) ≠ w(e′) for e ≠ e′. Find a spanning tree T = (V, E′) of the graph G such that the total weight w(T) is minimum.

Borůvka’s algorithm

1. Initially all edges of G are uncolored and let each vertex of G be a trivial blue tree.

2. Repeat the following coloring step until there is only one blue tree.

3. Coloring step: For every blue tree T, select the minimum-weight uncolored edge incident to T. Color all selected edges blue.

Proof (Correctness of Borůvka’s algorithm). It is easy to see that at the end of Borůvka’s algorithm the blue colored edges form a spanning tree (in each step the distinct edge-weights guarantee to get a blue forest containing all vertices). Now we show that the blue spanning tree obtained by Borůvka’s algorithm is the minimum spanning tree and that it is the only minimum spanning tree of the given graph G. Indeed, let T be a minimum spanning tree of G and let T^{∗} be the blue spanning tree obtained by the algorithm. We show that T = T^{∗}. Assume to the contrary T ≠ T^{∗}. Let e^{∗} be the first blue colored edge of T^{∗} which does not belong to T. Let P be the path in T joining the vertices of e^{∗}. It is clear that at the time when the edge e^{∗} gets blue color at least one of the edges, say e, of P is uncolored. By the algorithm w(e) > w(e^{∗}). However,

Figure 2: Last pages of paper [2]

then T − e + e^{∗} is a spanning tree with smaller weight, a contradiction. Thus T = T^{∗}.

This algorithm is called parallel merging or forest growing. It needs only log | V | iterations while each iteration needs | E | steps. The speed up of this (and other MST) algorithm was intensively studied, see, e.g., [16] for a survey.

4 Borůvka’s paper [2]

In the present terminology [1] is an outline of [2], and [2] is the full version of [1]. [2] is written in Czech with an extensive (6 pages) German summary. This also contributed to the fact that [2] is better known than [1]. The following is the translation of the beginning of the paper.

Dr. Otakar Borůvka

ON A CERTAIN MINIMUM PROBLEM

In this article I am presenting a solution of the following problem:

Let a matrix M of numbers r_{αβ}(α, β = 1, 2, …, n; n ≥ 2), all positive and pairwise different, with the exception of r_{αβ} = 0 and r_{αβ} = r_{βα} be given. From this matrix a set of nonzero and pairwise different numbers should be chosen such that

(1) For any p_{1}, p_{2} mutually different natural numbers ≤ n, it would be possible to choose a subset of the form

r_{p_{1}c_{2}}, r_{c_{2}c_{3}}, r_{c_{3}c_{4}}, …, r_{c_{q−2}c_{q−1}}, r_{c_{q−1}p_{2}}.

(2) The sum of its elements would be smaller than the sum of elements of any other subset of nonzero and pairwise different numbers, satisfying the condition (1).

Paper [2] then proceeds by constructing the solution. What was written in [1] in an easy way, takes in this paper a very complicated form and Borůvka needs four full pages (pages 37–40) to elaborately explain the first iteration of his algorithm.

Why does it take so long? In a private conversation Borůvka explained this in a contextual way: “I have been young, this was a very new and non-standard topic and thus I have been afraid that it will not be published. So I made it a little more mathematical”, [5]. That, of course, may be a part of the truth. Another reason is certainly the absence of good notation and mainly special notions (such as chain, path, or connectivity). Borůvka elaborately constructs each component of the first iteration by describing the corresponding forest by means of (sort of) a pointer machine: first he finds a maximum path P containing a given point then he starts with a new vertex and finds a maximum path P′ which either is disjoint with P or terminates in a vertex of P and so on. Then he combines these paths to tree-components.

In the iterative step he already proceeds more easily (page 41). The final set is denoted by J. The author then verifies all the properties of the set J. This is (on page 41) divided into 5 theorems (numbered I, II, III, IV, V) which are proved in the rest of the paper on p. 43–52. The proofs, of course, follow the elaborate construction of the set J.

The paper ends (p. 51) with a remark on a geometric interpretation (in kdimensions) of the result and an example of the solution for a particular planar set with 74 points is given. The German summary covers the construction of the set J and states Theorems I, II, III, IV, V.

It is interesting to note that at three places of the article (in the proof of Theorem III) he arrives on p. 46 to the exchange axiom in the following rudimental form

K′′ ≡ K′ − [mq], [mn].

He does not, of course, mention cycles (as in Whitney) or more general algebraic setting (as in Van der Waerden). That had to wait another decade (and this is covered in another article of this book, see [7]).

Borůvka’s approach is a brute force approach par excellence. Not knowing any related literature (and there was almost none, graph theory and even al-

Figure 3: Proof of Theorem III, paper [2]

gorithms were not yet born^{1}) and feeling that the problem is very new, he produced a solution. On the way he arrived at the key exchange axiom which is in the heart of all greedy-type algorithms for MST. He was just solving a concrete engineering problem and in a stroke of a genius he isolated the key statement of contemporary combinatorial optimization. But he certainly was not a Moravian engineer (as it is sometimes erroneously claimed). He was rather an important and well connected mathematician (see Section 6).

5 Vojtěch Jarník [11]

Borůvka was lucky. His contribution was recognised and his article [2] has been quoted by both Kruskal [14] and Prim [19] – papers which became the standard references in the renewed interest in the MST in sixties. [2] became the most quoted paper of Borůvka. The first reaction to Borůvka came however almost immediately from Vojtěch Jarník [11]. Paper [11] published in the same journal, has the same title as [2] which is explained by its subtitle “from a letter to O. Borůvka‘”^{2}. This paper has only five pages with two pages of German summary. The paper begins as follows:

1For comparison, König’s book appeared in 1936. It is interesting to note that König describes his book as “absolute graph theory” and neither optimization (i.e., MST) nor enumeration is covered by this book.

Documenta Mathematica · Extra Volume ISMP (2012) 127–141

In your article “About a minimum problem” (Práce moravské přírodovědecké společnosti, svazek III, spis 3) you solved an interesting problem. It seems to me that there is yet another, and I believe, simpler solution. Allow me to describe to you my solution.

Let n elements be given, I denote them as numbers 1, 2, …, n. From these elements I form \frac{1}{2}n(n − 1) pairs [i, k], where i ≠ k; i, k = 1, 2, …, n. I consider the pair [k, i] identical with pair [i, k]. To every pair [i, k] let there be associated a positive number r_{i,k}(r_{i,k} = r_{k,i}). Let these numbers be pairwise different.

We denote by M the set of all pairs [i, k]. For two distinct natural numbers p, q ≤ n, I call a chain (p, q) any set of pairs from M of the following form:

[p, c_{1}], [c_{1}, c_{2}], [c_{2}, c_{3}], …, [c_{s−1}, c_{s}], [c_{s}, q]  (1)

Also a single pair [p, q] I call a chain (p, q).

A subset H of M I call a complete subset (kč for short) if for any pair of distinct natural numbers p, q ≤ n, there exists a chain (p, q) in H (i.e., a chain of form (1) all of whose pairs belong to H). There are kč; as M itself is kč.

If

[i_{1}, k_{1}], [i_{2}, k_{2}], …, [i_{t}, k_{t}]  (2)

is a subset K of set M, we put

∑_{j=1}^{t} r_{i_{j},k_{j}} = R(K).

If for a complete set K the value R(K) is smaller than or equal to the values for all other complete sets , then I call K a minimal complete set in M (symbolically mkč). As there exists at least one kč and there are only finitely many kč, there exists at least one mkč. The problem, which you solved in your paper, can be formulated as follows:

Problem: Prove that there exists a unique mkč and give a formula for its construction.

Remark: Sets satisfying (1) are, of course now, called path, trail, walk; Jarník considers (1) as a family – repetitions are allowed). Of course kč corresponds to spanning connected subgraphs and mkč corresponds to minimum

2This also explains an unusual “Ich form” of the article.

Documenta Mathematica · Extra Volume ISMP (2012) 127–141

Figure 4: Jarník’s formula for MST

spanning tree. There is no mention of trees in this paper. However, in the proof Jarník defines “connected set of entries‘”. These definitions are key to his simplification of Borůvka. On p. 60 Jarník begins to decribe his solution:

Let us now introduce a certain subset J of M as follows:

Definition of set J. J = [a_{1}, a_{2}], [a_{3}, a_{4}], …, [a_{2n−3}, a_{2n−2}] where a_{1}, a_{2}, … are defined as follows:

First step. Choose as a_{1} any of elements 1, 2, …, n. Let a_{2} be defined by the relation

r_{a_{1},a_{2}} = min r_{a_{1},l} (l = 1, 2, …, n; l ≠ a_{1}).

k-th step. Having defined

a_{1}, a_{2}, a_{3}, …, a_{2k−3}, a_{2k−2}(2 ≤ k < n)  (5)

we define a_{2k−1}, a_{2k} by r_{a_{2k−l},a_{2k}} = min r_{i,j} where i ranges over all numbers a_{1}, a_{2}, …, a_{2k−2} and j ranges over all the remaining numbers from 1, 2, …, n. Moreover, let a_{2k−1} be one of the numbers in (5) such that a_{2k} is not among the numbers in (5). It is evident that in this procedure exactly k of the numbers in (5) are different, so that for k < n the k-th step can be performed.

The solution of our problem is then provided by the following:

Proposition:

1. J is mkč.

1. There is no other mkč.

1. J consists of exactly n − 1 pairs.

This construction is today called the tree growing procedure. It is usually called Prim’s algorithm [20]; to establish justice we call this in [17] (and elsewhere) the Jarník-Prim algorithm.

Jarník (1897–1970) was less lucky than Borůvka in the credits to his work in combinatorial optimization. His solution was almost entirely neglected until very recently, [6] being perhaps the earliest exception. Even more so: the same negligence (see, e.g., [8]) relates to his joint paper with Kössler [12] which is probably the earliest paper dealing with the Steiner Tree Problem (see [13] for history and additional information on this part of Jarník’s work). This is surprising because Jarník was (and still is) a famous mathematician. Already in 1930 (after two years in Göttingen with E. Landau) he was well known (and better known than Borůvka). It is interesting to note how quickly Jarník reacted to the “exotic” Borůvka paper. One can only speculate that this probably motivated him to continue (with Kössler) with the “Steiner tree problem” [12]. Like Borůvka, he never returned to these problems again.

6 Borůvka’s century

At the end of the last millenium more authors (e.g., G. Grass, I. Klíma, B.-H. Lévy) attempted to summarize the passing century as “my” century. But in a way, this was Borůvka’s century: born in 1899 he died in 1995. He was born to a middle class Czech family. His father Jan Borůvka was a respected school principal at his birthplace in Uherský Ostroh. He was elected a honorable citizien of the town. The school garden, which he founded, was a safe haven for young Otakar. He attended the school of his father and later the gymnasium in Uherské Hradiště. He excelled in all subjects. This was already during the First World War (1914–1918) and on the advice of his parents, Borůvka switched to the military gymnasium in Hranice and then to military academy in Mödling (near Vienna). As he recollects, the sole reason of this was to escape the military draft during the war. While he respected good teachers at both institutions, he did not like this period very much (riding a horse being an

Figure 5: Otakar Borůvka (archive of the authors)

exception). So immediatelly after the end of the war he resigned and returned home to independent Czechoslovakia. He continued his studies at the Technical University in Brno and then at the Masaryk University in Brno. It is there where he met professor Matyáš Lerch. Lerch (1860–1922) was perhaps the first modern Czech mathematician who obtained the prestigeous Grand Prix de Academie de Paris in 1900, published over 230 papers and was in contact with leading mathematicians of his time (he also attended the old gymnasium in Rakovník, a dear place to the authors of this article). Lerch chose Borůvka as his assistant in 1921 and had a profound influence on him. Borůvka writes that possibly thanks to Lerch he became a mathematician. He considered himself as the heir to Lerch’s legacy and initiated in 1960 the installment of Lerch’s memorial plaque in Brno. Unfortunately, Lerch died early in 1922. However, at that time Borůvka was fortunate to meet another strong mathematician, Eduard Čech (1893–1960), and he became his assistant in 1923. Čech, a few years Borůvka’s senior and very active person in every respect, suggested to him to start working in differential geometry. Čech asked Borůvka to complete some computations in his ongoing work and to become acquainted with what was then a very new method of rapère mobile of Elie Cartan. Borůvka succeeded and was rewarded by Čech who arranged his stay in Paris during the academic year 1926/27.

Before this, in winter 1925/26, Borůvka met Jindřich Saxel, an employee of Západomoravské elektrárny (West-Moravian Powerplants), who was not academically educated and yet suggested to Borůvka a problem related to electrification of South-West Moravia. Borůvka remembers ([4], p. 52) that in the solution he was inspired by Lerch’s attitude towards applications and that he worked intensively on the problem. We already know the outcome of this. In spring 1927 Borůvka lectured in Paris about [2] at a seminar (of Cambridge mathematician J. L. Coolidge). He writes: “despite (and perhaps because of) this very unconventional topic, the lecture was received very well with an active discussion” ([4], p. 59). In Paris he worked intensively with E. Cartan and became a lifelong friend of Cartan’s family (particularly of his son Henri, future president of IMU, whom Borůvka invited to Brno in 1969).

Back in Brno, in winter 1927/28, Borůvka passed a habilitation (with a thesis on the Γ-function and, again on a suggestion of E. Čech, obtained a Rockefeller scholarship to Paris for the academic year 1929/30. In Paris he continued his research motivated by intensive contacts with E. Cartan and met other leading mathematicians of his time (J. Hamadard, B. Segre, É. Picard, M. Fréchet, É. Goursat, H. Lebesgue). After one year in Paris he received (thanks to involvement of E. Cartan “in whose interest it was to expand his methods to Germany” [4], p. 67) the Rockefeller scholarship to Hamburg.

In Hamburg he visited W. Blaschke but Borůvka mentions also E. Artin, H. Zassenhaus, E. Kähler and E. Sperner. It is interesting to note that S. S. Chern followed Borůvka’s path a few years later (from Hamburg 1934, to Paris 1936). Chern quoted Borůvka and “even called some statements by my name” ([4], p. 67). This is also the case with, e.g., the Frenet-Borůvka theorem, see [10].

In 1931 Borůvka returned to Brno and stayed there basically for the rest of his life. He was then 32, had spent at least four years abroad meeting many of the eminent mathematicians of his time. He was an individualist (typically not writing joint papers). This is illustrated by the fact that although Čech invited him to take part in his newly founded (and later internationally famous) topological seminar in Brno, he declined. But Borůvka was an influential teacher. He progressed steadily at the university and in the society. However, the war which broke out in 1939 brought many changes to Borůvka’s life. All Czech universities were closed by the Nazis. Borůvka and his circle of friends were arrested by the Gestapo at Christmas 1941. In his memoirs [4], he recalls this at length in the chapter called “On the threshold of death”. Among others, his friend Jindřich Saxel was executed in 1941. It is interesting to note, that the West-Moravian Powerplants recollected Borůvka’s work on MST and made him a generous job offer (which he declined).

During his life, Borůvka changed his research topic several times. He was fully aware of his position in Brno and took responsibility for the future development there. He wrote basic books on group theory and groupoids (during the World War II). After the war he started his seminar on differential equations.

[4] contains contributions of his students in all areas of his activities. Due to the space limitations and the scope of this article we end the his-

torical overview of Borůvka’s century here. Borůvka was deeply rooted in the Moravian soil. For Brno mathematics he was the founding father. Not in the

Figure 6: Borůvka’s grave at the Central Cemetery in Brno

sense of politics (which he luckily avoided most of his life) but in the sense of scientific activity which by far transcended the provincial focus of Brno of his time. In this respect he can be compared, e.g., to Leoš Janáček. This is not a mere speculation: Borůvka played several instruments and the conductor Zdeněk Chalabala was a close friend to both Janáček and Borůvka.

The authors of this text knew Borůvka in his last years. He was a grand old man, yet modest, and still interested in the new developments. He was aware of his MST fame. He would be certainly pleased to know that the late J. B. Kruskal immediately replied to an invitation to write a memorial article on Borůvka [15]. The quiet strength of Borůvka is felt even posthumously. Fig. 6 depicts Borůvka’s remarkable grave at the Central Cemetery in Brno.

Acknowledgement. Supported by the grant ERC-CZ 1201 CORES.

References

[1] O. Borůvka, Příspěvěk k řešení otázky ekonomické stavby elektrovodných sítí (Contribution to the solution of a problem of economical construction of electrical networks), Elektronický obzor 15 (1926), 153–154.

[2] O. Borůvka, O jistém problem minimálním (About a certain minimum problem), Práce morav. přírodověd. spol. v Brně III (3) (1926), 37–58 (in Czech, German summary).

[3] O. Borůvka, Několik vzpomínek na matematický život v Brně (Some recollections of the mathematical life in Brno), Pokroky matematiky, fyziky a astronomie 22 (1977), 91–99.

[4] O. Borůvka (ed. J. Malina), Universitas Masarykiana, Granos Plus, Brno 1996, ISBN 80-902004-0-0.

[5] O. Borůvka, Personal communications and discussions with J. Nešetřil (around 1980).

[6] K. Čulík and V. Doležal and M. Fiedler, Kombinatorická analýza v praxi, SNTL, Prague, 1967.

[7] W. H. Cunningham, The Coming of the Matroids, this volume.

[8] R. L. Graham and M. Grötschel and L. Lovász (eds.), Handbook of Combinatorics, North-Holland, Amsterdam, 1995.

[9] R. L. Graham and P. Hell, On the history of the minimum spanning tree problem, Ann. History Comput. 7 (1985), 43–57.

[10] P. A. Griffits, Some Reflexions on the Mathematical Contributions of S. S. Chern, in: S. S. Chern, S. – Y. Cheng, G. Tian, P. Li (eds.), A mathematician and his mathematical work: selected papers of S.S. Chern, Springer 1978, 76 – 82.

[11] V. Jarník, O jistém problem minimálním, Práce morav. přírodověd. spol. v Brně VI (4) (1930), 57–63.

[12] V. Jarník and M. Kössler, O minimálních grafech obsahujících n daných bodů, Čas. pro pěstování matematiky 63 (1934), 223–235.

[13] B. Korte and J. Nešetřil, Vojtěch Jarník’s work in combinatorial optimization, Discrete Mathematics 235 (2001), 1–17.

[14] J. B. Kruskal, On the shortest spanning subtree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc. 7 (1956), 48–50.

[15] J. B. Kruskal, A reminiscence about shortest spanning subtrees, Arch. Math. 33 (1–2) (1997), 13–14.

[16] M. Mareš, The saga of minimum spanning trees, Computer Sci. Review 2 (2008), 165–221.

[17] J. Matoušek and J. Nešetřil, Invitation to discrete mathematics, Oxford Univ. Press, Oxford 1998, 2008 [18] J. Nešetřil, Some remarks on the history of MST-problem, Arch. Math. 33

(1997), 15–22.

[19] J. Nešetřil and E. Milková and H. Nešetřilová, Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history, (2001), 3–36.

[20] R. C. Prim, The shortest connecting network and some generalization, Bell Systems Tech. J. 36 (1957), 1389–1401.

[21] Arch. Math. (a special Borůvka issue) 33, 1–2, (1997).

[22] A. Schrijver, On the history of combinatorial optimization (till 1960), in: K. Aardal, G.L. Nemhauser, R. Weismantel (eds.), Handbook of Discrete Optimization Elsevier, Amsterdam, 2005, 1–68.

[23] R. E. Tarjan, Data Structures and Network algorithms, SIAM, 1987.

Jaroslav Nešetřil IUUK, Faculty of Mathematics and Physics Charles University Malostranské nám. 25 118 00 Prague 1 Czech Republic

    nesetril@kam.mff.cuni.cz

Helena Nešetřilová

PEF, Czech University for Life Sciences Kamýcká 129 165 21 Prague 6 Czech Republic

                                      helena.nesetrilova@gmail.com

142

Documenta Mathematica · Extra Volume ISMP (2012)