Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Date Reviewed: Jan 1 1985

Perhaps, like others who received most of their formal higher education in the 1950s, I became interested in graph theory as a consequence of the gradual realization that it was difficult, if not impossible, to apply the computer to any problem of any substantial complexity without being immediately involved in some aspect or another of graph theory. It began to seem that as a rule computing problems of any interest were :Iessentially combinatorial.

In the early 1950s, one’s introduction to combinatorics was normally viewed merely as a necessary preliminary to the study of statistics; graph theory, if it was taught at all, was on the other hand definitely pure mathematics, a collection of charming puzzles (Konigsberg bridge problem, four color conjecture) unrelated to the real world. Even down to the present day, the field of combinatorics retains this personality split between those who are interested in combinatorial problems for their own sake and those who are interested in them because they want to do something efficiently on the computer.

Under Math Reviews (MR) category 05C Graph Theory, we find the advice, "for application of graphs, see 68Q, 68R, 94C," refering us to Theory of Computing, Discrete Mathematics in Relation to Computer Science, and Circuits and Networks, respectively.

It is particularly in this context that the book by Gondran and Minoux is so welcome and important: it does a marvelous joub of relating the :Itheory of graphs to dozens, if not hundreds, of everyday computational problems, whether numeric or nonnumeric in nature. It is a book that neither the practicing computer scientist nor the pure graph theorist can fail to profit and learn from. The authors have therefore succeeded admirably in their main objective: to create "a synthesis...," "...a panorama, as complete as possible, of the theory and its applications up to the very last few years," and "...a point of balance between theory and practice."

Success, however, does not imply recognition, as I discovered when I tried to locate the French original [1]. Although it had been favorably reviewed (MR 82g:68062), a computer search failed to locate it in any Canadian university (including French-language ones). As far as I could determine, it is available in Canada at only one location (Canada Institute for Scientific and Technical Information). Professor Vajda has therefore performed an especially valuable service in making this book available to what will surely be a much wider audience.

There are twelve chapters and five appendices (one evidently added in translation) with the following titles:

C1 Generalities about Graphs C2 The Shortest Path Problem in a Graph C3 Path Algebras C4 Trees and Arborescences C5 Flows and Transortation Networks C6 Flows with Gains, Multicommodity Flows C7 Matchings and b-Matchings C8 Eulerian and Hamiltonian Walks C9 Matroids C10 Non-Polynomial Problems C11 Branch and Bound Algorithms C12 Approximate Algorithms

A1 Linear Programming A2 Integer Linear Programming A3 Lagrangean Relaxation and Solving the Dual Problem A4 Dynamic Programming A5 Minimum Ration Problems. These titles convey well the scope of the material which :IGraphs and Algorithms fits into a unified framework. They do not, however, convey:

*1DThe compactness of the development. (In each chapter a few usually easily-proved theorems usually suffice to support the subsequent algorithms.) *1DThe wealth of examples, used both for clarification and motivation. *1DThe diversity and the computational relevance of the problems (232 altogether). *1DThe wide coverage of the references, both in time and by topic. *1DThe natural stages by which we are led to perceive the relations among problems and algorithms.

The book is excellent, but it is not perfect. Certain topics, such as planarity testing and minimax problems, are given rather short shrift; although I agree not everything can be covered in 650 pages. Solutions are not included for the problems (though for many of them it could fairly be argued that they are included to stimulate further research by the student rather than to yield right or wrong answers). The book contains its fair share of typos, minor slips slips, unintentional abuses of language, inadvertently undefined terms, or moderately awkward Gallicisms :V- I would estimate at least on every two pages :V- but none interfere very seriously with the flow of information and ideas; indeed, as I have suggested above, much of the development is notable for its elegance (the handling of trees, of flow problems, and of matroids springs to mind in this context). The major flaw is traditional bane of books written in french: the index. The index of this English translation is at least an improvement on the indices of most French-language technical books, but it is also considerably worse (less complete, less accurate) than the index one would expect to find in the average technical book pulished today in North America.

But these are really quibbles. :IGraph and algorithms is one of those rare and precious books that really pulls an area of knowledge together. I look forward to using sections of its as the basis of graduate and advanced undergraduate courses in "applied combinatorics" or "applications of graph theory" for years to come, and I expect to refer to it often for help in the computer solution of real world problems.

Reviewer:  W. F. Smyth Review #: CR108721
Bookmark and Share
 
Graph Theory (G.2.2 )
 
 
Combinatorics (G.2.1 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Numerical Algorithms And Problems (F.2.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Theory": Date
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
Efficient graph automorphism by vertex partitioning
Fowler G., Haralick R., Gray F., Feustel C., Grinstead C. Artificial Intelligence 21(1-2): 245-269, 1983. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy