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.
be a finite list of nonnegative integers that is in nonincreasing lexicographical order and let
be a pair of nonnegative integers with
is digraphic if and only if the finite list
has nonnegative integer pairs and is digraphic.
is arbitrarily with the exception of pairs
digraphic then the theorem will be applied at most
times setting in each further step
This process ends when the whole list
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
cannot be reduced to a list
of nonnegative integer pairs in any step of this approach, the theorem proves that the list
The algorithm is based on the following theorem.
be a finite list of nonnegative integers such that
is maximal with respect to the lexicographical order under all pairs
is digraphic if and only if the finite list
has nonnegative integer pairs and is digraphic.
must not be in lexicographical order as in the first version.
is digraphic, then the theorem will be applied at most
times, setting in each further step
This process ends when the whole list
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
of nonnegative integer pairs in any step of this approach, the theorem proves that the list