Topic summary
Graph algorithms
Extracted from the Wikipedia article List of algorithms.
Graph algorithms
- Blossom algorithm: algorithm for constructing maximum-cardinality matching on graphs.
- Coloring algorithm: algorithms for graph (vertex or edge) coloring (subject to constraints, e.g. proper coloring or list coloring)
- Hopcroft–Karp algorithm: convert a bipartite graph to a maximum-cardinality matching
- Hungarian algorithm: algorithm for finding a perfect matching
- Prüfer coding: conversion between a labeled tree and its Prüfer sequence
- Tarjan's off-line lowest common ancestors algorithm: computes lowest common ancestors for pairs of nodes in a tree
- Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies.