Kleitman–Wang algorithms

(Redirected from Kleitman–Wang 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.

Kleitman–Wang algorithm (arbitrary choice of pairs)

edit

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.

Kleitman–Wang algorithm (maximum choice of a pair)

edit

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.

See also

edit

References

edit
  • 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