Jump to content

User:David Eppstein/Graph Algorithms

From Wikipedia, the free encyclopedia
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
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
Graph partition
Kernighan–Lin algorithm
Tree decomposition
Branch-decomposition
Path decomposition
Planar separator theorem
Graph minors
Courcelle's theorem
Robertson–Seymour theorem
Bidimensionality