User:David Eppstein/Graph Algorithms
| ||||||||
Graph Algorithms
[edit]- Introduction
- Graph theory
- Glossary of graph theory
- Undirected graphs
- Directed graphs
- Directed acyclic graphs
- Computer representations of graphs
- 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 for general vertex connectivity
- 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
- 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
- Vertex cover
- Dominating set
- Feedback vertex set
- Feedback arc set
- Tours
- Eulerian path
- Hamiltonian path
- Hamiltonian path problem
- Travelling salesman problem
- Bottleneck traveling salesman problem
- Christofides' heuristic for the TSP
- Chinese postman 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
- Application: Sociograms
- Application: Concept maps
- Special classes of graphs
- Interval graph
- Chordal graph
- Perfect graph
- Intersection graph
- Unit disk graph
- Line graph
- Claw-free graph
- Median graph