Graph theory algorithms
The Kleitman–Wang algorithms are two different algorithms in graph theory solving the digraph realization problem, i.e. the question if there exists for a finite list of nonnegative integer pairs a simple directed graph such that its degree sequence is exactly this list. For a positive answer the list of integer pairs is called "digraphic". Both algorithms construct a special solution if one exists or prove that one cannot find a positive answer. These constructions are based on recursive algorithms. Kleitman and Wang gave these algorithms in 1973.
Kleitman–Wang algorithm (arbitrary choice of pairs).
The algorithm is based on the following theorem.
Let formula_1 be a finite list of nonnegative integers that is in nonincreasing lexicographical order and let formula_2 be a pair of nonnegative integers with formula_3. List formula_4 is digraphic if and only if the finite list formula_5 has nonnegative integer pairs and is digraphic.
Note that the pair formula_2 is arbitrarily with the exception of pairs formula_7. If the given list formula_4 digraphic then the theorem will be applied at most formula_9 times setting in each further step formula_10. This process ends when the whole list formula_11 consists of formula_12 pairs. In each step of the algorithm one constructs the arcs of a digraph with vertices formula_13, i.e. if it is possible to reduce the list formula_4 to formula_11, then we add arcs formula_16. When the list formula_4 cannot be reduced to a list formula_11 of nonnegative integer pairs in any step of this approach, the theorem proves that the list formula_4 from the beginning is not digraphic.
Kleitman–Wang algorithm (maximum choice of a pair).
The algorithm is based on the following theorem.
Let formula_1 be a finite list of nonnegative integers such that formula_21 and let formula_2 be a pair such that formula_23 is maximal with respect to the lexicographical order under all pairs formula_24. List formula_4 is digraphic if and only if the finite list formula_26 has nonnegative integer pairs and is digraphic.
Note that the list formula_4 must not be in lexicographical order as in the first version. If the given list formula_4 is digraphic, then the theorem will be applied at most formula_9 times, setting in each further step formula_10. This process ends when the whole list formula_11 consists of formula_12 pairs. In each step of the algorithm, one constructs the arcs of a digraph with vertices formula_13, i.e. if it is possible to reduce the list formula_4 to formula_11, then one adds arcs formula_36. When the list formula_4 cannot be reduced to a list formula_11 of nonnegative integer pairs in any step of this approach, the theorem proves that the list formula_4 from the beginning is not digraphic.
References.
 ;templatestyles src="Reflist/styles.css" / ;