Fulkerson–Chen–Anstee (Digraph Realization Problem Graph Realization Problems)

From Algorithm Wiki
Jump to navigation Jump to search

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