Wikipedia:Books/archive/Graph Algorithms
Introduction
- Graph theory
- Glossary of graph theory terms
- Undirected graph
- Directed graph
- Directed acyclic graphs
- Graph (abstract data type)
- Adjacency list
- Adjacency matrix
- Implicit graph
Graph exploration and vertex ordering
- Depth-first search
- Breadth-first search
- Lexicographic breadth-first search
- Iterative deepening depth-first search
- Topological sorting
- Application:Dependency Graphs
Connectivity of undirected graphs
- Connected components
- Edge connectivity
- Vertex connectivity
- Menger's theorems on edge and vertex connectivity
- Ear decomposition
- Algorithms for 2-edge-connected components
- Algorithms for 2-vertex-connected components
- Algorithms for 3-vertex-connected components
- Karger's algorithm
Connectivity of directed graphs
- Strongly connected components
- Tarjan's strongly connected components algorithm
- Path-based strong component algorithm
- Kosaraju's strongly connected components algorithm
- Reachability
- Transitive closure
- Transitive reduction
- Application: 2-satisfiability
Shortest paths
- Shortest path problem
- Dijkstra's algorithm for single-source shortest paths with positive edge lengths
- Bellman–Ford algorithm for single-source shortest paths allowing negative edge lengths
- Johnson's algorithm for all-pairs shortest paths in sparse graphs
- Floyd–Warshall algorithm for all-pairs shortest paths in dense graphs
- Suurballe's algorithm for two shortest disjoint paths
- Bidirectional search
- A* search algorithm
- Longest path problem
- Widest path problem
- Canadian traveller problem
- K shortest path routing
- Application: Centrality analysis of social networks
- Application: Schulze voting system
Minimum spanning trees
- Minimum spanning tree
- Borůvka's algorithm
- Kruskal's algorithm
- Prim's algorithm
- Edmonds's algorithm for directed minimum spanning trees
- Degree-constrained spanning tree
- Maximum-leaf spanning tree
- K-minimum spanning tree
- Capacitated minimum spanning tree
- Capacitated minimum spanning tree
- Application: Single-linkage clustering
- Application: Maze generation
Cliques, independent sets, and coloring
- Clique problem
- Bron–Kerbosch algorithm for listing all maximal cliques
- Independent set problem
- Maximal independent set
- Graph coloring
- Bipartite graph
- Greedy coloring
- Application: Register allocation
Covering and domination
Tours
- Eulerian path
- Hamiltonian path
- Hamiltonian path problem
- Travelling salesman problem
- Bottleneck traveling salesman problem
- Christofides' heuristic for the TSP
- Route inspection problem
Matching
- Matching
- Hopcroft–Karp algorithm for maximum matching in bipartite graphs
- Edmonds's algorithm for maximum matching in non-bipartite graphs
- Assignment problem
- Hungarian algorithm for the assignment problem
- FKT algorithm for counting matchings in planar graphs
- Stable marriage problem
- Stable roommates problem
- Permanent
- Computing the permanent
Network flow
- Maximum flow problem
- Max-flow min-cut theorem
- Ford–Fulkerson algorithm for maximum flows
- Edmonds–Karp algorithm for maximum flows
- Dinic's algorithm for maximum flows
- Push–relabel maximum flow algorithm
- Closure problem
- Minimum-cost flow problem
Graph drawing and planar graphs
- Planar graph
- Dual graph
- Fáry's theorem
- Steinitz's theorem
- Planarity testing
- Left-right planarity test
- Graph drawing
- Force-directed graph drawing
- Layered graph drawing
- Upward planar drawing
- Graph embedding
- Sociogram
- Concept map
Special classes of graphs
- Interval graph
- Chordal graph
- Perfect graph
- Intersection graph
- Unit disk graph
- Line graph
- Claw-free graph
- Median graph
Graph isomorphism
- Graph isomorphism
- Graph isomorphism problem
- Graph canonization
- Subgraph isomorphism problem
- Color-coding
- Induced subgraph isomorphism problem
- Maximum common induced subgraph
- Maximum common edge subgraph
Graph decomposition and graph minors