Getting the download link through email is temporarily not available. Please check back later.
To get the free app, enter your mobile phone number.
Data Structures and Network Algorithms (CBMS-NSF Regional Conference Series in Applied Mathematics)
Use the Amazon App to scan ISBNs and compare prices.
Best Books of the Year So Far in fiction, nonfiction, mysteries, children's books, and much more.
Customers Who Bought This Item Also Bought
Discover books for all types of engineers, auto enthusiasts, and much more. Learn more
Top Customer Reviews
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.Read more ›
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.