Data Structures and Network Algorithms (CBMS-NSF Regional Conference Series in Applied Mathematics) [Paperback]

Robert Endre Tarjan (Author)

Book Description

ISBN-10: 0898711878 | ISBN-13: 978-0898711875 | Publication Date: January 1, 1987

There has been an explosive growth in the field of combinatorial algorithms. These algorithms depend not only on results in combinatorics and especially in graph theory, but also on the development of new data structures and new techniques for analyzing algorithms. Four classical problems in network optimization are covered in detail, including a development of the data structures they use and an analysis of their running time. Data Structures and Network Algorithms attempts to provide the reader with both a practical understanding of the algorithms, described to facilitate their easy implementation, and an appreciation of the depth and beauty of the field of graph algorithms.

Editorial Reviews

Book Description

There has been an explosive growth in the field of combinatorial algorithms. These algorithms depend not only on results in combinatorics and especially in graph theory, but also on the development of new data structures and new techniques for analyzing algorithms. Four classical problems in network optimization are closely examined.

Product Details

• Paperback: 140 pages
• Publisher: Society for Industrial Mathematics (January 1, 1987)
• Language: English
• ISBN-10: 0898711878
• ISBN-13: 978-0898711875
• Product Dimensions: 9.8 x 6.7 x 0.3 inches
• Shipping Weight: 7.8 ounces
• Average Customer Review: 4.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #872,680 in Books (See Top 100 in Books)
  • #69 in Books > Computers & Technology > Programming > Algorithms > Data Structures

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

24 of 24 people found the following review helpful:

5.0 out of 5 stars Deservedly a classic, March 23, 2000

By 

Tom Morrisette (New York City, USA) - See all my reviews

This review is from: Data Structures and Network Algorithms (CBMS-NSF Regional Conference Series in Applied Mathematics) (Paperback)

This is a superb book. I taught a graduate level course based on it at Lehigh University in 1984 or 1985. It was awarded the prestigious annual Lanchester prize for book of the year Operations Research Society of America about that time. Robert Tarjan was awarded the ACM's Turing award, computer sciences closest equivalent to the Nobel Prize for his contibutions to the theory of algorithms. This book is an excellent introduction to his work. The algorithms in this book were state of the art when it was published, but I don't know how close they are to today's best.

Most of the optimal algorithms in the book grew out of Tarjan's pioneering work on algorithms that minimizes total complexity by allowing individual chunks of work to consume large amounts of computing resources if they build up "credits" that make subsequent steps more efficient. Until Tarjan used this approach to develop superior algorithms for a number of classical problems, the state of the art had been to limit the resources consumed by each step and bound total complexity by multipying the number of steps by the worst case resource consumption per step.

Tarjan's exposition illustrates the power of abstraction. He uses abstract data types throughout, carefully defining them in terms of their fundamental operations. This approach will be very natural for anyone familiar with object oriented programming.

There is a huge amount of information in very few pages, but it is organized very well. Often Tarjan's carefully chosen words say a lot more than is apparent to casual reader's. I spent one 75 minute period explaining his 12 line proof of one of his algorithms. Then the class demanded that I illustrate how the algorithm actually worked on a real problem, so we spent another 1.5 classes applying the algorithm to a small problem I contrived to exercise all of its boundary conditions.

Other faculty advised me that this book was much too hard for course intended for advanced undergraduate and beginning graduate students, but the students disagreed. More than one commented that the material was hard after first reading, but that after hearing my lectures and rereading their assignments, they realized that it was really pretty easy and that the book presented it well. Most would have appreciated worked out examples to observe the dynamic behavior of the algorithms. One student animated some of the algorithms and went on to write his masters thesis on algorithm animation.

11 of 11 people found the following review helpful:

4.0 out of 5 stars Very clearly written, July 14, 1999

By A Customer

This review is from: Data Structures and Network Algorithms (CBMS-NSF Regional Conference Series in Applied Mathematics) (Paperback)

A network here mean a graph with with weighted, undirected edges. This short (113 page) book is written in a clear style, and could be used as a textbook, athough it does not include exercises. Emphasis is placed on proving the efficiency of the algorithms presented. No knowlege of graph theory or algorithms is assumed, but knowlege of basic programming and college-entry level math is required.

The first half of the book covers the data structures used in solving the network problems that are presented in the second half. These data structures including disjoint sets, heaps, and search trees. Highlights of this half of the book are Tarjan's proof of the amoritized cost of union find, and explaination of self-adjusting binary trees.

The second half of the book covers four classical network problems: minimum spanning tree, shortest paths, network flows (e.g. min-cut), and matchings.

I found the first half of the book more interesting, because more of it was new to me, and because it seemed more likely to be of practical value to me in my work. I have seen presentations of the network problems before, but not with the analysis of efficiency, and comparison of different approaches.

Robert Tarjan (the author) has written many papers on efficient graph algorithms, and appears to be a pioneer in applying proofs of efficiency to graph algorithm. He is often cited in reference to the efficient graph algorithms he has discovered.

This book was published in 1983, but does not seem to be dated.