Algorithm Study - aragorn/home GitHub Wiki

Problems

• assignment problem
• clustering
• estimating probability
  • simple beta distribution

Bipartite

• https://en.wikipedia.org/wiki/Bipartite_graph

• Characterization

  • A graph is bipartite if and only if it does not contain an odd cycle.
  • A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).
  • The spectrum of a graph is symmetric if and only if it's a bipartite graph.

• https://en.wikipedia.org/wiki/Matching_(graph_theory)

  • See Definition section. matched, maximal matching, maximum matching, perfect matching, near perfect matching.
  • In weighted bipartite graphs, finding a maximum weighted bipartite matching is known as the assignment problem.

Flow network

• https://en.wikipedia.org/wiki/Flow_network

Assignment Problem

• https://en.wikipedia.org/wiki/Assignment_problem
• https://en.wikipedia.org/wiki/Hungarian_algorithm

Clustering

• https://en.wikipedia.org/wiki/Hierarchical_clustering
• https://en.wikipedia.org/wiki/Single-linkage_clustering

Estimating Probability

• https://en.wikipedia.org/wiki/Beta_distribution
• http://egloos.zum.com/nullmodel/v/3790240