Methods for the graph realization problem

DOI10.2478/ausi-2023-0017OpenAlexW4389623434MaRDI QIDQ6152848

Csaba György Pătcaş, Zoltán Kása, Pál Aurel Kupán

Publication date: 13 February 2024

Published in: Acta Universitatis Sapientiae. Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2478/ausi-2023-0017

zbMATH Keywords

degree sequencesflow networksbigraphical listsgraph realization algorithmsgraphical listsmodified Edmonds-Karp algorithm

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• A short constructive proof of the Erdős-Gallai characterization of graphic lists
• A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
• A simple criterion on degree sequences of graphs
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Efficient generation of graphical partitions
• Dominance order and graphical partitions
• Algorithms for constructing graphs and digraphs with given valences and factors
• A remark on the existence of finite graphs
• Degree-based graph construction
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Constructing and sampling directed graphs with given degree sequences
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Methods for the graph realization problem