Kleitman–Wang algorithms: Difference between revisions

Revision as of 18:01, 7 March 2016

Revision as of 15:23, 20 September 2020

Line 1:

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 graphDirected_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|1973}}</ref> gave these algorithms in 1973.

==Kleitman–Wang algorithm (arbitrary choice of pairs)==