Graph Algorithms

Introduction Königsberg problem Graph theory Glossary of graph theory terms Undirected graph Directed graph Directed acyclic graphs (DAG) Graph Representations and Data Structures Graph (abstract data type) Adjacency list Adjacency matrix Incidence matrix Implicit graph Graph Exploration and Vertex Ordering Depth-first search (DFS) Breadth-first search (BFS) 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 (2-SAT) Planar Graphs and Graph Drawing Planar Graphs Planar graph Dual graph Fáry's theorem Steinitz's theorem Planarity testing Left-right planarity test Graph Drawing Graph drawing Force-directed graph drawing Layered graph drawing Upward planar drawing Graph embedding Sociogram Concept map 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 Ramsey's theorem 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 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 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 minor Courcelle's theorem Robertson–Seymour theorem Bidimensionality __NOEDITSECTION__