references good graph theory textbooks include [ ][ ][ ]and [ more advanced topicsincluding the more careful attention to running timesare covered in [ ][ ]and [ use of adjacency lists was advocated in [ the topological sort algorithm is from [ ]as described in [ dijkstra' algorithm appeared in [ the improvements using -heaps and fibonacci heaps are described in [ and [ ]respectively the shortest-path algorithm with negative edge weights is due to bellman [ ]tarjan [ describes more efficient way to guarantee termination ford and fulkerson' seminal work on network flow is [ the idea of augmenting along shortest paths or on paths admitting the largest flow increase is from [ other approaches to the problem can be found in [ ][ ][ ][ ][ ][ ]and [ an algorithm for the min-cost flow problem can be found in [ an early minimum spanning tree algorithm can be found in [ prim' algorithm is from [ ]kruskal' algorithm appears in [ two (|elog log | |algorithms are [ and [ the theoretically best-known algorithms appear in [ ][ ][ and [ an empirical study of these algorithms suggests that prim' algorithmimplemented with decreasekeyis best in practice on most graphs [ the algorithm for biconnectivity is from [ the first linear-time strong components algorithm (exercise appears in the same paper the algorithm presented in the text is due to kosaraju (unpublishedand sharir [ other applications of depth-first search appear in [ ][ ][ ]and [ (as mentioned in the results in [ and [ have been improvedbut the basic algorithm is unchangedthe classic reference work for the theory of np-complete problems is [ additional material can be found in [ the np-completeness of satisfiability is shown in [ and independently by levin the other seminal paper is [ ]which showed the np-completeness of problems an excellent survey of complexity theory is [ an approximation algorithm for the traveling salesman problemwhich generally gives nearly optimal resultscan be found in [ solution to exercise can be found in [ solutions to the bipartite matching problem in exercise can be found in [ and [ the problem can be generalized by adding weights to the edges and removing the restriction that the graph is bipartite efficient solutions for the unweighted matching problem for general graphs are quite complex details can be found in [ ][ ]and [ exercise deals with planar graphswhich commonly arise in practice planar graphs are very sparseand many difficult problems are easier on planar graphs an example is the graph isomorphism problemwhich is solvable in linear time for planar graphs [ no polynomial time algorithm is known for general graphs ahoj hopcroftand ullmanthe design and analysis of computer algorithmsaddison-wesleyreadingmass ahujak melhornj orlinand tarjan"faster algorithms for the shortest path problem,journal of the acm ( ) - bellman"on routing problem,quarterly of applied mathematics ( ) - boruvka"ojistem problemu minimalnim (on minimal problem),praca moravske prirodo-vedecke spolecnosti ( ) -