The PhD Thesis of Martin Mareš

Or: The Saga of Minimum Spanning Trees

I have written my PhD thesis on graph algorithms, models of computation and especially minimum spanning trees and ranks of combinatorial structures. My advisor is Jaroslav Nešetřil, my opponents include Josep Diaz, Václav Koubek, and Patrice Ossona de Mendez.

You can download the whole thesis (PDF), or its extended abstract (PDF) or slides from the defense (PDF).

There is also a revised version (2022-04-25) which contains a couple of corrections of minor errors. (However, the typography of this version is not so fine-tuned as in the original.)

The source text in TEX is also accessible in my GIT repository at git://git.ucw.cz/saga.git, including full log of changes.

Preface

This thesis tells the story of two well-established problems of algorithmic graph theory: the minimum spanning trees and ranks of permutations. At distance, both problems seem to be simple, boring and already solved, because we have polynomial-time algorithms for them since ages. But when we come closer and seek algorithms that are really efficient, the problems twirl and twist and withstand many a brave attempt at the optimum solution. They also reveal a vast and diverse landscape of a deep and beautiful theory. Still closer, this landscape turns out to be interwoven with the intricate details of various models of computation and even of arithmetics itself.

I have tried to cover all known important results on both problems and unite them in a single coherent theory. At many places, I have attempted to contribute my own little stones to this mosaic: several new results, simplifications of existing ones, and last, but not least filling in important details where the original authors have missed some.

When compared with the earlier surveys on the minimum spanning trees, most notably Graham and Hell and Eisner, this work adds many of the recent advances, the dynamic algorithms and also the relationship with computational models. No previous work covering the ranking problems in their entirety is known.

The early parts of this thesis also served as a basis for a course on graph algorithms which I was teaching at our faculty during years 2006 and 2007. They are included in the textbook which I have written for this course.

So, my gentle reader, let us nestle deep in an ancient wing armchair. The saga of the graph algorithms begins …

Journal version

A slightly polished version of the chapters on minimum spanning trees has been published Computer Science Review, Volume 2, Issue 3, Elsevier, 2008, pp. 165-221.

See the publisher's page for more.

This page is maintained by Martin Mareš