On Erdős-Gallai and Havel-Hakimi algorithms

Details On Erdős-Gallai and Havel-Hakimi algorithms On Erdős-Gallai and Havel-Hakimi algorithms

2011-11-14

arxiv.org/abs/1111.3282v1

Acta Univ. Sapientiae, Inform. 3, 2 (2011) 230--268

Computer Science

Discrete Mathematics

Scientific paper

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 $\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 this quick algorithm we computed the number of the different degree sequences of simple graphs for $24, ...,29$ vertices.

Affiliated with

Also associated with

No associations

Rating

On Erdős-Gallai and Havel-Hakimi algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Erdős-Gallai and Havel-Hakimi algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Erdős-Gallai and Havel-Hakimi algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218886