TY - GEN
T1 - An Efficient Algorithm to Generate All Labeled Graphs with a Given Graphical Degree Sequence
AU - Wang, Kai
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
PY - 2025/8/12
Y1 - 2025/8/12
N2 - We present a simple and efficient algorithm that generates all labeled graphs with a given graphical degree sequence. The algorithm does not discard any isomorphic duplicates during the generation process. It works by constructing a conceptual search tree each of whose leaf nodes represents a labeled realization of the input sequence. Furthermore, a natural lexicographical ordering is imposed on the labels of the vertices of the constructed graphs so that a corresponding lexicographical ordering is induced on all labeled realizations of the input sequence and the algorithm generates all outputs in this ordering. The algorithm can also be easily parallelized.
AB - We present a simple and efficient algorithm that generates all labeled graphs with a given graphical degree sequence. The algorithm does not discard any isomorphic duplicates during the generation process. It works by constructing a conceptual search tree each of whose leaf nodes represents a labeled realization of the input sequence. Furthermore, a natural lexicographical ordering is imposed on the labels of the vertices of the constructed graphs so that a corresponding lexicographical ordering is induced on all labeled realizations of the input sequence and the algorithm generates all outputs in this ordering. The algorithm can also be easily parallelized.
KW - combinatorial generation
KW - graphical degree sequence
KW - labeled graph
KW - labeled realization
UR - https://www.scopus.com/pages/publications/105014456555
U2 - 10.1007/978-3-031-95130-5_4
DO - 10.1007/978-3-031-95130-5_4
M3 - Conference article
AN - SCOPUS:105014456555
SN - 9783031951299
T3 - Communications in Computer and Information Science
SP - 40
EP - 52
BT - Computational Science and Computational Intelligence - 11th International Conference, CSCI 2024, Proceedings
A2 - Arabnia, Hamid R.
A2 - Deligiannidis, Leonidas
A2 - Shenavarmasouleh, Farzan
A2 - Amirian, Soheyla
A2 - Ghareh Mohammadi, Farid
PB - Springer Science and Business Media Deutschland GmbH
T2 - 11th International Conference on Computational Science and Computational Intelligence, CSCI 2024
Y2 - 11 December 2024 through 13 December 2024
ER -