Combinatorial algorithms are algorithms that deal with combinatorial structures, which are sets, ordered n-tuples, and any structures that can be built from them, like graphs.
Combinatorial algorithms include algorithms for:
- Generation: List all structures of a given type, such as combinations and permutations, connected components of a graph
- Search: Find at least one structure with a given property
- Optimisation and approximation algorithms can be used to solve search problems
- Optimisation methods for search problems include exhaustive search, backtracking, branch and bound, and dynamic programming
- Approximation methods include greedy algorithms
- Subsets
- Subsets using Gray codes
- Partitions
- Cartesian product
- Permutations
- Combinations
- Multicombinations
- Combinations of a multiset
- Subsets of a multiset
- K-permutations
- Spanning forest
- Spanning tree
- Labeled trees
- Breadth-first search
- Realising a degree sequence
- Topological sort
- Complement of a graph
- Bellman-Ford algorithm
- Floyd-Warshall algorithm
- Dijkstra’s algorithm
- Boruvka’s minimal spanning tree algorithm
- Kruskal’s minimal spanning tree algorithm
- Prim’s minimal spanning tree algorithm
- Cycle detection
- Spanning trees
- Connected components
- Euler circuits
- Hamiltonian circuits
- Traveling salesman problem using backtracking
- Maximum clique using backtracking
- Vertex colouring using backtracking