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} |