User:David Eppstein/Graph Algorithms
 | The Wikimedia Foundation's book rendering service has been withdrawn. Please upload your Wikipedia book to one of the external rendering services. |
 | You can still create and edit a book design using the Book Creator and upload it to an external rendering service:
|
| This user book is a user-generated collection of Wikipedia articles that can be easily saved, rendered electronically, and ordered as a printed book. If you are the creator of this book and need help, see Help:Books (general tips) and WikiProject Wikipedia-Books (questions and assistance). Edit this book: Book Creator · Wikitext Order a printed copy from: PediaPress [ About ] [ Advanced ] [ FAQ ] [ Feedback ] [ Help ] [ WikiProject ] [ Recent Changes ] | ||||||||
Graph Algorithms
- 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
- 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
- Gabow's strongly connected components algorithm
- Kosaraju's strongly connected components algorithm
- 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
- Bidirectional search
- A* search algorithm
- Longest path problem
- Canadian traveller problem
- 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
- 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
- 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
- Fraysseix–Rosenstiehl's planarity criterion
- Graph drawing
- Force-based algorithms (graph drawing)
- Graph embedding
- Book embedding
- Application: Sociograms
- Application: Dependency diagrams of software modules
- 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 subgraph isomorphism problem
- Graph decomposition and graph minors
- Graph minors
- Forbidden graph characterization
- Planar separator theorem
- Tree decomposition
- Branch-decomposition
- Path decomposition
- Robertson–Seymour theorem