• Home
    Tables – Mathematics – Combinatorial Algorithms

    Backtracking AlgorithmA general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot be possibly extended to a valid solution.
    Bitmanupulation AlgorithmA class of combinatorial algorithm that operates on integer data at the level of its individual bits.
    Traveling Salesman Problem (TSP)An algorithmic problem focused on optimization. In this context, it is a measure of the shortest possible route that a traveling salesman can take to cover a given set of cities and return to the origin city.
    Hamiltonian Cycle AlgorithmAn algorithm finding a route in a graph that visits each vertex exactly once and then returns to the start.
    Maximum Flow AlgorithmAn Algorithm used to find the greatest possible flow through a network.
    Chinese Postman ProblemAn algorithm to find a shortest closed path or circuit that visits every edge of a graph.
    Graph Coloring AlgorithmAn algorithm where each vertex is assigned a color in a way that no two adjacent vertices share the same color.
    Graph Traversal (BFS & DFS)An algorithm for traversing or searching tree or graph data structures. It starts at the root and explores nodes at the present level before moving on to nodes at the next level.
    Greedy AlgorithmAn algorithm that makes the locally optimal choice at each stage with the hope of finding a global optimum.
    Stable Marriage ProblemAn algorithm solving the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element.
    Dijkstra’s AlgorithmAn algorithm for finding the shortest paths between nodes in a graph.
    Kruskal’s AlgorithmAn algorithm to find a minimum spanning tree for a connected and undirected graph.
    Prim’s AlgorithmA greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.
    Huffman CodingA popular algorithm for encoding data using variable-length binary strings.
    Johnson’s AlgorithmAn algorithm that finds all the shortest paths between every pair of vertices in a sparse, edge weighted, directed graph.
    Floyd Warshall AlgorithmAn algorithm for finding shortest paths in a weighted graph with positive or negative edge weights, but no negative cycles.
    Bellman Ford AlgorithmAn algorithm very similar to Dijkstra’s, but it can also handle negative numbers.
    Ford-Fulkerson AlgorithmAn algorithm that tackles the maximum flow problem: how much flow we can push through a network.
    KMP (Knuth-Morris-Pratt) AlgorithmA linear time complexity algorithm used to find the presence of a pattern in a text.
    Rabin-Karp AlgorithmA string-searching method that uses hashing for efficient search.