<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>The graph realization problem seeks an answer to how and under what conditions a graph can be constructed if we know the degrees of its vertices. The problem was widely studied by many authors and in many ways, but there are still new ideas and solutions. In this sense, the paper presents the known necessary and su cient conditions for realization with the description in pseudocode of the corresponding algorithms. Two cases to solve the realization problem are treated: finding one solution, and finding all solutions. In this latter case a parallel approach is presented too, and how to exclude isomorphic graphs from solutions. We are also discussing algorithms using binary integer programming and flow networks.</p>
<p>In the case of a bigraphical list with equal out- and in-degree sequences a modified Edmonds–Karp algorithm is presented such that the resulting graph will be always symmetric without containing loops. This algorithm solves the problem of graph realization in the case of undirected graphs using flow networks.</p>
</abstract>

The graph realization problem seeks an answer to how and under what conditions a graph can be constructed if we know the degrees of its vertices. The problem was widely studied by many authors and in many ways, but there are still new ideas and solutions. In this sense, the paper presents the known necessary and su cient conditions for realization with the description in pseudocode of the corresponding algorithms. Two cases to solve the realization problem are treated: finding one solution, and finding all solutions. In this latter case a parallel approach is presented too, and how to exclude isomorphic graphs from solutions. We are also discussing algorithms using binary integer programming and flow networks.
In the case of a bigraphical list with equal out- and in-degree sequences a modified Edmonds–Karp algorithm is presented such that the resulting graph will be always symmetric without containing loops. This algorithm solves the problem of graph realization in the case of undirected graphs using flow networks.

Methods for the graph realization problem

Sapientia Hungarian University of Transylvania

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"Methods for the graph realization problem"}

The graph realization problem seeks an answer to how and under what conditions a graph can be constructed if we know the degrees of its vertices. The problem...

Methods for the graph realization problem

Publié en ligne: 12 déc. 2023

Pages: 267 - 293

DOI: https://doi.org/10.2478/ausi-2023-0017

Mots clés
degree sequences, graph realization algorithms, flow networks, graphical lists, bigraphical lists, modified Edmonds–Karp algorithm

© 2023 Zoltán Kása et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Methods for the graph realization problem

Publié en ligne: 12 déc. 2023

Pages: 267 - 293

DOI: https://doi.org/10.2478/ausi-2023-0017

Mots clésdegree sequences, graph realization algorithms, flow networks, graphical lists, bigraphical lists, modified Edmonds–Karp algorithm

© 2023 Zoltán Kása et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Mots clés
degree sequences, graph realization algorithms, flow networks, graphical lists, bigraphical lists, modified Edmonds–Karp algorithm