Graph realization problem

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Solutions Graph realization problem_section_0

Other notations Graph realization problem_section_1

Related problems Graph realization problem_section_2

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

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

The second is known as the digraph realization problem. Graph realization problem_sentence_2

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. Graph realization problem_sentence_3

The general problem is still unsolved. Graph realization problem_sentence_4

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: realization problem.