Full index

All the pages of the website, in the order of the menu: the chapters with their sections and the other pages.

Graphs

• 1. Graphs · Exercises
  • 1.1 Undirected and directed graphs
  • 1.2 Representations of a graph
  • 1.3 Connectivity
  • 1.4 Trees and forests
  • 1.5 The rank of the incidence matrix
  • 1.6 Graph search
  • 1.7 Typical mistakes
  • 1.8 In summary

Trees and paths

• 2. Minimum spanning trees · Exercises
  • 2.1 The minimum spanning tree problem
  • 2.2 Cuts and cycles
  • 2.3 The cut property and the cycle property
  • 2.4 The generic greedy algorithm
  • 2.5 Kruskal's algorithm
  • 2.6 Prim's algorithm
  • 2.7 Uniqueness of the minimum spanning tree
  • 2.8 Typical mistakes
  • 2.9 In summary
• 3. Shortest paths · Exercises
  • 3.1 Shortest path problems
  • 3.2 Optimality conditions and potentials
  • 3.3 The linear programming formulation
  • 3.4 Shortest paths in acyclic graphs
  • 3.5 The Bellman–Ford algorithm
  • 3.6 Dijkstra's algorithm
  • 3.7 Typical mistakes
  • 3.8 In summary

Flows

• 4. Network flow models · Exercises
  • 4.1 Networks and flows
  • 4.2 The minimum cost flow model
  • 4.3 Feasibility conditions
  • 4.4 Removing the lower bounds
  • 4.5 Unbalanced instances
  • 4.6 Total unimodularity and integrality
  • 4.7 The dual model and the reduced costs
  • 4.8 Special cases
  • 4.9 A transshipment instance
  • 4.10 Typical mistakes
  • 4.11 In summary
• 5. Maximum flow · Exercises
  • 5.1 The maximum flow problem
  • 5.2 Cuts
  • 5.3 The residual network
  • 5.4 The max-flow min-cut theorem
  • 5.5 The Ford–Fulkerson algorithm
  • 5.6 The Edmonds–Karp algorithm
  • 5.7 Applications
  • 5.8 Typical mistakes
  • 5.9 In summary
• 6. Minimum cost flow · Exercises
  • 6.1 The residual network with costs
  • 6.2 Circulations and their decomposition
  • 6.3 Negative cycle optimality conditions
  • 6.4 Optimality conditions with potentials
  • 6.5 A first feasible flow
  • 6.6 The cycle-canceling algorithm
  • 6.7 The successive shortest path algorithm
  • 6.8 Typical mistakes
  • 6.9 In summary
• 7. Transportation and assignment · Exercises
  • 7.1 The transportation problem
  • 7.2 Basic solutions
  • 7.3 Initial basic feasible solutions
  • 7.4 The potential method
  • 7.5 The assignment problem
  • 7.6 Typical mistakes
  • 7.7 In summary

Network simplex

• 8. The network simplex · Exercises
  • 8.1 The simplex algorithm on the minimum cost flow model
  • 8.2 Bases and spanning trees
  • 8.3 Potentials and optimality
  • 8.4 The pivot
  • 8.5 The network simplex algorithm
  • 8.6 An uncapacitated example
  • 8.7 Degeneracy and strongly feasible trees
  • 8.8 A capacitated example with a degenerate pivot
  • 8.9 The initial tree: Phase 0
  • 8.10 Typical mistakes
  • 8.11 In summary

Project management

• 9. Project management · Exercises
  • 9.1 Projects and project networks
  • 9.2 Paths and critical paths
  • 9.3 The forward pass: earliest times
  • 9.4 The backward pass: latest times
  • 9.5 Slacks and critical activities
  • 9.6 The critical path method
  • 9.7 The linear programming model
  • 9.8 Two critical paths and changes of durations
  • 9.9 Typical mistakes
  • 9.10 In summary

Other pages

• Exercises
• Lab
• Downloads