Elsevier < Decision Sciences Publications < Handbooks in Operations Research and Management Science < Volume 3: Computing < Chapter 8

COMPUTING
Edited by E.G. Coffman, Jr., J.K. Lenstra and A.H.G. Rinnooy Kan

CHAPTER 8
Design (with Analysis) of Efficient Algorithms
D. Gusfield

1. Introduction*  

2. Maximum network flow on a sequential machine

3. Ford-Fulkerson leads 'naturally' to Dinits

4. The breakdown of phases: Goldberg's preflow-push algorithm

5. Parametric flow: The value of amortizing across phases

6. Computing edge connectivity: The amortization theme writ small

7. Matching: Optimal, greedy and optimal-greedy approaches

8. Parallel network flow in O(n2 log n) time

9. Distributed algorithms

10. Many-for-one results

11. The power of preprocessing: The least common ancestor problem

12. Randomized algorithms for matching problems

13. A matching problem from biology illustrating dynamic programming

14. Min-cost flow: Strong versus weak polynomial time

15. Weighted node cover: Approximation algorithms based on network flow

16. Summary and thesis

Acknowledgement

References

* The first two pages of the chapters are available as PDF file.

 Complete chapters on ScienceDirect

[Description and order information]

Important links:

• Member Order Form
  
• Proposals for further Handbook Volumes
  

Related Websites:

• Decision Sciences Publications
• Handbooks in Information Systems
• Handbooks in Economics
• Handbooks in Finance

<< back