Kleitman–Wang Algorithm (Digraph Realization Problem Graph Realization Problems)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(n)$

Space Complexity

$O(n)$ words

(Derived: Space complexity bounded by time complexity; keep track of a constant number of sets of size $O(n)$)

Description

Constructs graph

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1973

Reference

https://linkinghub.elsevier.com/retrieve/pii/0012365X7390037X