# Graph realization problem

Jump to navigation
Jump to search

## Solutions

## Other notations

## Related problems

Similar problems describe the degree sequences of simple bipartite graphs or the degree sequences of simple directed graphs.

The first problem is the so-called bipartite realization problem.

The second is known as the digraph realization problem.

The problem of constructing a solution for the graph realization problem with the additional constraint that each such solution comes with the same probability was shown to have a polynomial-time approximation scheme for the degree sequences of regular graphs by Cooper, Martin, and Greenhill.

The general problem is still unsolved.

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Graph realization problem.