View source for Kleitman–Wang algorithms

{{Short description|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 (abstract data type)|list]] of nonnegative [[integer]] pairs a [[directed graph|simple directed graph]] such that its [[Directed_graph#Degree_sequence|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 [[Recursion (computer science)|recursive algorithm]]s. Kleitman and Wang <ref>{{harvtxt|Kleitman|Wang|1973}}</ref> gave these algorithms in 1973.

==Kleitman–Wang algorithm (arbitrary choice of pairs)==
The algorithm is based on the following theorem.

Let <math>S=((a_1,b_1),\dots,(a_n,b_n))</math> be a finite list of nonnegative integers that is in [[nonincreasing]] [[lexicographical order]] and let <math>(a_i,b_i)</math> be a pair of nonnegative integers with <math>b_i >0</math>. List <math>S</math> is digraphic if and only if the finite [[Enumeration|list]] <math>S'=((a_1-1,b_1),\dots,(a_{b_i-1}-1,b_{b_i-1}),(a_{b_i},0),(a_{b_i+1},b_{b_i+1}),(a_{b_i+2},b_{b_i+2}),\dots,(a_n,b_n))</math> has nonnegative integer pairs and is digraphic.

Note that the pair <math>(a_i,b_i)</math> is arbitrarily with the exception of pairs <math>(a_j,0)</math>. If the given list <math>S</math> digraphic then the theorem will be applied at most <math>n</math> times  setting in each further step <math>S:=S'</math>. This process ends when the whole list <math>S'</math> consists of <math>(0,0)</math> pairs. In each step of the algorithm one constructs the [[directed graph|arcs]] of a digraph with vertices <math>v_1,\dots,v_n</math>, i.e. if it is possible to reduce the list <math>S</math> to <math>S'</math>, then we add arcs <math>(v_i,v_1),(v_i,v_2),\dots,(v_{i},v_{b_i-1}),(v_i,v_{b_i+1})</math>. When the list <math>S</math> cannot be reduced to a list <math>S'</math> of nonnegative integer pairs in any step of this approach, the theorem proves that the list <math>S</math> from the beginning is not digraphic.

==Kleitman–Wang algorithm (maximum choice of a pair)==
The algorithm is based on the following theorem.

Let <math>S=((a_1,b_1),\dots,(a_n,b_n))</math> be a finite list of nonnegative integers such that <math>a_1 \geq a_2 \geq \cdots \geq a_n</math> and let <math>(a_i,b_i)</math> be a pair such that <math>(b_i,a_i)</math> is maximal with respect to the [[lexicographical order]] under all pairs <math>(b_1,a_1),\dots,(b_n,a_n)</math>. List <math>S</math> is digraphic if and only if the finite list <math>S'=((a_1-1,b_1),\cdots,(a_{b_i-1}-1,b_{b_i-1}),(a_{b_i},0),(a_{b_i+1},b_{b_i+1}),(a_{b_i+2},b_{b_i+2}),\dots,(a_n,b_n))</math> has nonnegative integer pairs and is digraphic.

Note that the list <math>S</math> must not be in lexicographical order as in the first version. If the given list <math>S</math> is digraphic, then the theorem will be applied at most <math>n</math> times, setting in each further step <math>S:=S'</math>. This process ends when the whole list <math>S'</math> consists of <math>(0,0)</math> pairs. In each step of the algorithm, one constructs the [[directed graph|arcs]] of a digraph with vertices <math>v_1,\dots,v_n</math>, i.e. if it is possible to reduce the list <math>S</math> to <math>S'</math>, then one adds arcs <math>(v_i,v_1),(v_i,v_2),\dots,(v_i,v_{b_i-1}),(v_i,v_{b_i+1})</math>. When the list <math>S</math> cannot be reduced to a list <math>S'</math> of nonnegative integer pairs in any step of this approach, the theorem proves that the list <math>S</math> from the beginning is not digraphic.

==See also==
*[[Fulkerson–Chen–Anstee theorem]]

==References==
*{{citation
| last1 = Kleitman | first1 = D. J.
| last2 = Wang | first2 = D. L.
| title = Algorithms for constructing graphs and digraphs with given valences and factors
| journal = Discrete Mathematics
| volume = 6
| year = 1973
| pages = 79–88
 | doi=10.1016/0012-365x(73)90037-x| doi-access = free
}}
{{reflist}}

{{DEFAULTSORT:Kleitman-Wang algorithms}}

[[Category:Graph algorithms]]