Graphs, networks and algorithms
type: Item
instance of: scholarly article
title: Graphs, networks and algorithms
zbMATH Open document ID: 1126.68058
DOI: 10.1007/978-3-540-72780-4
author: Dieter Jungnickel
published in: Algorithms and Computation in Mathematics
publication date: 2007-06-08T00:00:00Z
review text: The first English edition of this book, in 1998 (see Zbl 0931.05001), was based on a translation of the third edition of the author's German text [Graphen, Netzwerke und Algorithmen (1987; Zbl 0644.05001)]. The second edition in 2005 (see Zbl 1061.05001) added material on the network simplex method and the five-colour theorem. The third edition of this standard textbook contains further new material on graphical codes and their decoding, and many additional exercises. Recent developments for the travelling salesman problem are presented as well. At the same time, the presentation has been updated and minor corrections have been carried out. The chapters cover basic graph theory, algorithms and complexity, shortest paths, spanning trees, the greedy algorithm, flows, combinatorial applications, connectivity and depth first search, colorings, circulations, the network simplex method, the synthesis of networks, matchings, and the travelling salesman problem. The three appendices include a list of some related NP-complete problems, solutions for most of the chapter exercises, and a list of symbols used in the text. The book provides a comprehensive list of references. Appendix B, containing sample solutions for exercises, is of particular value. The solutions are concise and elegant, and integrate well with the presentation. The writing is clear and precise. The underlying mathematics is treated carefully, and developed well. The focus on algorithmic issues motivates challenging questions, and connects the presentation to many real applications. These make the text appropriate for computer science and engineering students, in addition to students of mathematics. The diversity of applications represented is a real strength of the text. While the author has more than adequately treated the conventional applications of graph-theoretic algorithms in networks, the topics treated are much broader. This in turn provides connections to other areas of mathematics, and application…
reviewed by: Charles J. Colbourn
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68-01
Mathematics Subject Classification ID: 05-01
Mathematics Subject Classification ID: 05Cxx
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5163313
zbMATH Keywords: algorithm
zbMATH Keywords: graph theory
zbMATH Keywords: complexity
zbMATH Keywords: network
zbMATH Keywords: tree
zbMATH Keywords: path
zbMATH Keywords: flow
zbMATH Keywords: colouring
zbMATH Keywords: matching
zbMATH Keywords: simplex method
zbMATH Keywords: graphical code
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-3-540-72780-4
OpenAlex ID: W2058653097
Recommended article: Graphs, networks and algorithms. Based on the translation of the 3rd German edition by Tilla Schade in collaboration with the author
Recommended article: Q4083324
Recommended article: Q5314567
Recommended article: Graphs, Algorithms, and Optimization
Recommended article: Q4004084
Recommended article: Q4003439
Recommended article: Q4220637
Recommended article: Q3684121
Recommended article: Q3628775
Recommended article: Q4840182
description: scientific article; zbMATH DE number 5163313