Graphs, networks and algorithms. Transl. from the 3rd German edition by Tilla Schade (Q1272253): Difference between revisions

This clearly written text treats a broad range of topics in graph theory and combinatorial optimization. It is suitable for an upper-level undergraduate or a lower-level graduate course. The approach is algorithmic, emphasizing combinatorial techniques (over, say, polyhedral ones), yet at the same time providing solid mathematical background, with most standard results proved in detail. It gives practical motivation for, and real applications of, most results and algorithms. The topics include spanning trees, shortest paths, matroids and the greedy algorithm, flows and circulations, matchings, depth first search and connectivity, colourings, and the traveling salesman problem. Many nice exercises are included, some with solutions.