Wikipedia:Books/archive/Graph Algorithms: Difference between revisions
< Wikipedia:Books | archive
Content deleted Content added
fixed more links Tag: |
Fixed links in the minimum spanning tree section Tag: |
||
| Line 43: | Line 43: | ||
Shortest paths |
Shortest paths |
||
*[[Shortest path problem]] |
*[[Shortest path problem]] |
||
*[[Dijkstra's algorithm for single-source shortest paths with positive edge lengths]] |
*[[Dijkstra's algorithm|Dijkstra's algorithm for single-source shortest paths with positive edge lengths]] |
||
*[[Bellman–Ford algorithm for single-source shortest paths allowing negative edge lengths]] |
*[[Bellman–Ford algorithm|Bellman–Ford algorithm for single-source shortest paths allowing negative edge lengths]] |
||
*[[Johnson's algorithm for all-pairs shortest paths in sparse graphs]] |
*[[Johnson's algorithm|Johnson's algorithm for all-pairs shortest paths in sparse graphs]] |
||
*[[Floyd–Warshall algorithm for all-pairs shortest paths in dense graphs]] |
*[[Floyd–Warshall algorithm|Floyd–Warshall algorithm for all-pairs shortest paths in dense graphs]] |
||
*[[Suurballe's algorithm for two shortest disjoint paths]] |
*[[Suurballe's algorithm|Suurballe's algorithm for two shortest disjoint paths]] |
||
*[[Bidirectional search]] |
*[[Bidirectional search]] |
||
*[[A* search algorithm]] |
*[[A* search algorithm]] |
||
| Line 54: | Line 54: | ||
*[[Canadian traveller problem]] |
*[[Canadian traveller problem]] |
||
*[[K shortest path routing]] |
*[[K shortest path routing]] |
||
*[[Application: Centrality analysis of social networks]] |
*[[Centrality|Application: Centrality analysis of social networks]] |
||
*[[Application: Schulze voting system]] |
*[[Schulze method|Application: Schulze voting system]] |
||
Minimum spanning trees |
Minimum spanning trees |
||
| Line 62: | Line 62: | ||
*[[Kruskal's algorithm]] |
*[[Kruskal's algorithm]] |
||
*[[Prim's algorithm]] |
*[[Prim's algorithm]] |
||
*[[Edmonds's algorithm for directed minimum spanning trees]] |
*[[Edmonds' algorithm|Edmonds's algorithm for directed minimum spanning trees]] |
||
*[[Degree-constrained spanning tree]] |
*[[Degree-constrained spanning tree]] |
||
*[[Maximum-leaf spanning tree]] |
*[[Connected dominating set|Maximum-leaf spanning tree]] |
||
*[[K-minimum spanning tree]] |
*[[K-minimum spanning tree]] |
||
*[[Capacitated minimum spanning tree]] |
*[[Capacitated minimum spanning tree]] |
||
*[[Capacitated minimum spanning tree]] |
*[[Capacitated minimum spanning tree]] |
||
*[[Application: Single-linkage clustering]] |
*[[Single-linkage clustering|Application: Single-linkage clustering]] |
||
*[[Application: Maze generation]] |
*[[Maze generation algorithm|Application: Maze generation]] |
||
Cliques, independent sets, and coloring |
Cliques, independent sets, and coloring |
||
Revision as of 20:35, 4 February 2023
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