Diaz:
> 2: simplify, remove proof sketches
-- 3: intro: replace "efficient" by "linear"
-- 3.1.7, 3.1.10: skip proof
-- 3.3: do we really need the full Komlos's result?
-- 3.3.17: maxflow: shouldn't Karzanov be cited, too?
-- 3.5.1: does the first alg give any insight?
-- 3.5.1: mention geometric distribution
-- 5.4.6: could we give a simple proof?
-- 5: mention graphs with moving vertices?
-- 6: mention d-regular graphs
-- 6: two monographs on Euclidean MST
- M. Steel: Probability theory and combinatorial optimization, SIAM 1997
- J. Yukich: Probability theory of classical Euclidean optimization problems, Springer 1998
+> 3.1.7, 3.1.10: skip proof
+> 3.5.1: does the first alg give any insight?
+> 5: mention graphs with moving vertices?
Patrice:
-- Remark on 2.5.1: polynomial time could be replaced by sub-exponential time.
+> Remark on 2.5.1: polynomial time could be replaced by sub-exponential time.
- For 1.5.6, you should probably quote D. Cheriton and R.E. Tarjan.
Finding Minimum Spanning Trees. SIAM J. on Comp. 5(4) (1976) pp.
724-742. who gave a linear time algorithm for planar graphs, extended by
Tarjan in 1983 to proper minor closed classes (both quoted by Gustedt).
[XXX: Cannot get the paper.]
-- In 3.1.12 and 3.1.16, you should make explicit the dependence of the
+> In 3.1.12 and 3.1.16, you should make explicit the dependence of the
running time with respect, for instance, to the Hadwiger number of the
graph or to the maximal density nabla(G) of a minor of the graph, as
considering a minor closed class or another does not change the