On Erd\H {o} s-Gallai and Havel-Hakimi algorithms
A Iványi, L Lucz, TF Móri, P Sótér - arXiv preprint arXiv:1111.3282, 2011 - arxiv.org
A Iványi, L Lucz, TF Móri, P Sótér
arXiv preprint arXiv:1111.3282, 2011•arxiv.orgHavel in 1955, Erd\H {o} s and Gallai in 1960, Hakimi in 1962, Ruskey, Cohen, Eades and
Scott in 1994, Barnes and Savage in 1997, Kohnert in 2004, Tripathi, Venugopalan and
West in 2010 proposed a method to decide, whether a sequence of nonnegative integers
can be the degree sequence of a simple graph. The running time of their algorithms is
$\Omega (n^ 2) $ in worst case. In this paper we propose a new algorithm called EGL (Erd\H
{o} s-Gallai Linear algorithm), whose worst running time is $\Theta (n). $ As an application of …
Scott in 1994, Barnes and Savage in 1997, Kohnert in 2004, Tripathi, Venugopalan and
West in 2010 proposed a method to decide, whether a sequence of nonnegative integers
can be the degree sequence of a simple graph. The running time of their algorithms is
$\Omega (n^ 2) $ in worst case. In this paper we propose a new algorithm called EGL (Erd\H
{o} s-Gallai Linear algorithm), whose worst running time is $\Theta (n). $ As an application of …
Havel in 1955, Erd\H{o}s and Gallai in 1960, Hakimi in 1962, Ruskey, Cohen, Eades and Scott in 1994, Barnes and Savage in 1997, Kohnert in 2004, Tripathi, Venugopalan and West in 2010 proposed a method to decide, whether a sequence of nonnegative integers can be the degree sequence of a simple graph. The running time of their algorithms is in worst case. In this paper we propose a new algorithm called EGL (Erd\H{o}s-Gallai Linear algorithm), whose worst running time is As an application of this quick algorithm we computed the number of the different degree sequences of simple graphs for vertices.
arxiv.org