View source for Fulkerson–Chen–Anstee (Digraph Realization Problem Graph Realization Problems)

== Time Complexity == 

$O(n)$

== Space Complexity == 

$O({1})$ words

(Derived: Checking an inequality that involves 3 summations, of max value $O(n^2)$ each (assuming max degree $\leq n$) which is $O(1)$ words in our Word RAM. We check this inequality for each $k = 1, \ldots, n$, but you can store the summations dynamically, so you only need to run $O(1)$ operations per iteration)

== Description == 

Makes use of (0,1) matrix properties, checks a property of the input values through the lens of an adjacency matrix

== Approximate? == 

Exact

== Randomized? == 

No, deterministic

== Model of Computation == 

Word RAM

== Year == 

1982

== Reference == 

https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/properties-of-a-class-of-01matrices-covering-a-given-matrix/9A3857D219511017536142BD7F132C91