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

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