TR-2011-11

Recognizing graphic degree sequences and generating all realizations

Zoltán Király



Abstract

In this paper we give a very simple, linear-time algorithm for deciding whether a given sequence of integers is graphic. We also give an implementation of the famous algorithm of Havel and Hakimi, which runs in $O(n\log\log n)$.
 
In the second half of the paper we present a new algorithm, which, given a graphic degree sequence, generates all graph realizations of this degree sequence. As the output may be exponential, this algorithm is not necessarily polynomial, but it is the first such algorithm with a polynomial delay, actually it runs with quadratic delay.


Bibtex entry:

@techreport{egres-11-11,
AUTHOR = {Kir{\'a}ly, Zolt{\'a}n},
TITLE = {Recognizing graphic degree sequences and generating all realizations},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {TR-2011-11}
}


Last modification: 9.1.2018. Please email your comments to Tamás Király!