Kleitman–Wang algorithms: Difference between revisions

Revision as of 18:01, 7 March 2016

Latest revision as of 19:56, 12 October 2024

(5 intermediate revisions by 5 users not shown)

Line 1:

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

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

Line 27 ⟶ 28:

| year = 1973

| pages = 79–88

| doi=10.1016/0012-365x(73)90037-x| doi-access = free
}}

{{reflist}}