Kleitman-Wang Algorithm

Get Kleitman%E2%80%93Wang Algorithm essential facts below. View Videos or join the Kleitman%E2%80%93Wang Algorithm discussion. Add Kleitman%E2%80%93Wang Algorithm to your PopFlock.com topic list for future reference or share this resource on social media.
## Kleitman-Wang algorithm (arbitrary choice of pairs)

## Kleitman-Wang algorithm (maximum choice of a pair)

## See also

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Kleitman%E2%80%93Wang Algorithm

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 ^{[1]} gave these algorithms in 1973.

The algorithm is based on the following theorem.

Let be a finite list of nonnegative integers that is in nonincreasing lexicographical order and let be a pair of nonnegative integers with . List is digraphic if and only if the finite list has nonnegative integer pairs and is digraphic.

Note that the pair is arbitrarily with the exception of pairs . If the given list digraphic then the theorem will be applied at most times setting in each further step . This process ends when the whole list consists of pairs. In each step of the algorithm one constructs the arcs of a digraph with vertices , i.e. if it is possible to reduce the list to , then we add arcs . When the list cannot be reduced to a list of nonnegative integer pairs in any step of this approach, the theorem proves that the list from the beginning is not digraphic.

The algorithm is based on the following theorem.

Let be a finite list of nonnegative integers such that and let be a pair such that is maximal with respect to the lexicographical order under all pairs . List is digraphic if and only if the finite list has nonnegative integer pairs and is digraphic.

Note that the list must not be in lexicographical order as in the first version. If the given list is digraphic, then the theorem will be applied at most times, setting in each further step . This process ends when the whole list consists of pairs. In each step of the algorithm, one constructs the arcs of a digraph with vertices , i.e. if it is possible to reduce the list to , then one adds arcs . When the list cannot be reduced to a list of nonnegative integer pairs in any step of this approach, the theorem proves that the list from the beginning is not digraphic.

- Kleitman, D. J.; Wang, D. L. (1973), "Algorithms for constructing graphs and digraphs with given valences and factors",
*Discrete Mathematics*,**6**: 79-88, doi:10.1016/0012-365x(73)90037-x

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists