Content deleted Content added
#suggestededit-add 1.0 Tags: Mobile edit Mobile app edit Android app edit |
m Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4 |
||
| (2 intermediate revisions by 2 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_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)==
| |||