\begin{filecontents*}{example.eps}
%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 19 19 221 221
%%CreationDate: Mon Sep 29 1997
%%Creator: programmed by hand (JK)
%%EndComments
gsave
newpath
  20 20 moveto
  20 220 lineto
  220 220 lineto
  220 20 lineto
closepath
2 setlinewidth
gsave
  .4 setgray fill
grestore
stroke
grestore
\end{filecontents*}

\documentclass{svjour3}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}

%
% Insert the name of "your journal" with
\journalname{CEJOR}
%

\begin{document}


\title{Parallel Erd\H os-Gallai algorithm}
\thanks{T\'AMOP}
%about the article that should go on the front page should be
%placed here. General acknowledgements should be placed at the end of the article.}


\titlerunning{Parallel Erd\H os-Gallai algorithm}    

\author{\mbox{Antal Iv\'anyi $^{1,3}$ \and  Lor\'and Lucz $^{2}$}}
%\thanks{The research of the first two authors was supported in part by OTKA grants K 60480, K 77420.}}

%\titlerunning{Short form of title}        % if too long for running head

\footnotetext[1]{Department of Computer Algebra, E\"otv\"os Lor\'and University. Mail: 1117 Budapest, 
P\'azm\'any P\'eter s\'et\'any 1/C, Hungary. E-mail: tony@compalg.inf.elte.hu}
\footnotetext[2]{Department of Computer Algebra, E\"otv\"os Lor\'and University. Mail: 1117 Budapest, 
P\'azm\'any P\'eter s\'et\'any 1/C, Hungary. E-mail: lorand.lucz@gmail.com}
\footnotetext[3]{Corresponding author}

\date{Received: \textbf{NOVEMBER 26, 2011} / Accepted: date}
% The correct dates will be entered by the editor

\maketitle

\begin{abstract}
Havel in 1955 \cite{Havel1955}, Erd\H os and Gallai in 1960 \cite{ErdosG1960}, Hakimi in 1962 \cite{Hakimi1962}, 
Tripathi, Venugopalan and West in 2010 \cite{TripathiVW2010} 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 in worst case is $\Omega(n^2).$ In \cite{IvanyiLMS2011Acta} the authors proposed a new 
algorithm called EGL (Erd\H os-Gallai Linear algorithm), whose worst running time is $\Theta(n).$ As an application of this linear 
time algorithm we describe Erd\H os-Gallai-Enumerative algorithm and using its parallel version   
enumerate the different degree sequences of simple graphs for 24, \ldots, 29 vertices (compare with \cite{Sloane2011A004251}).

\keywords{Degree sequences \and Graphical sequences \and Erd\H os-Gallai theorem \and Parallel algorithms} 
% \PACS{PACS code1 \and PACS code2 \and more}
\subclass{05C20, 05C85, 68R10}
%\and MSC code2 \and more}
\end{abstract}


\section{Introduction}\label{sec-intro}
In the practice an often appearing problem is the ranking of different objects as economical decisions, hardware or software 
products, cars, persons etc. A typical method of the ranking is the pairwise comparison of the objects, assignment 
of points to the objects and sorting the objects according to the sums of the numbers of the received points.

For example Landau \cite{Landau1953} references to biological, Hakimi \cite{Hakimi1962} to chemical, Kim et al. \cite{KimTME2009},  
Newman and Barab\'asi \cite{NewmanB2006} to net-centric, Anholzer, Boz\'oki, F\"ul\"op, Koczkodaj, Poesz, R\'onyai and Temesi to 
economical \cite{AnholzerBBK2011,BozokiFK2011,BozokiFP2011,BozokiFR2010,Temesi2011}, Liljeros et al. \cite{LiljerosEASA2001} to 
human applications, while Frank, Iv\'anyi, Lucz, M\'ori, S\'ot\'er and Pirzada 
\cite{Frank2011,Ivanyi2009,Ivanyi2010,IvanyiL2012Comb,IvanyiLMS2011Acta,IvanyiLM2011AML,IvanyiP2011} to applications in sports.  

Let $n \geq 1$. We will denote the degrees of a simple graph as $d = (d_1,\ldots,d_n)$. We call a sequence 
$b = (b_1, \ldots, b_n)$ $n$\textit{-bounded}, if $0 \leq b_i \leq n - 1$ for $i = 1,\ldots,n$, and \textit{n-regular}, if 
the conditions $n - 1 \geq b_1 \geq \cdots \geq b_n \geq 0$ hold, and $n$\textit{-even}, if the sum of the elements of $b$ 
is even. If there exists a graph with $n$ vertices which has the  
degree sequence $b$, then we say that $b$ is \textit{n-graphical}.

The main aim of this paper is to report on the parallel realization of the linear \textsc{Erd\H os-Gallai} algorithm. 
Although this problem is interesting in itself, for us the main motivation was our wish to answer the question formulated in the 
recent monograph \cite[Research problem 2.3.1]{Frank2011} Andr\'as Frank: "\textit{Decide if a sequence of n integers 
can be the final score of a football tournament of n teams.}" During testing and reconstructing of potential football 
sequences important subproblem is the handling of sequences of draws. And the problems "Is this sequence graphical?" and 
"Is this sequence a football draw sequence?" are equivalent, therefore the quick answer is vital for us.

The structure of the paper is as follows. After the introductory Section \ref{sec-intro} in Section \ref{sec-classical} 
we describe two classical quadratic testing algorithms, then in Section \ref{sec-linear} we explain a new linear time algorithm. 
Section \ref{sec-enumerating} contains the description of the enumerative version of the new linear algorithm, while in Section 
\ref{sec-parallel} its parallel implementation is explained. Finally  in the last Section \ref{sec-summary} we summarize the results. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Classical algorithms (Havel-Hakimi and Erd\H os-Gallai)}\label{sec-classical}
In this section we describe two classical testing algorithms due to V\'aclav Havel and Louis Hakimi, resp. 
Paul Erd\H os and Tibor Gallai. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Havel-Hakimi algorithm (HH) \label{subs-HH}}
This algorithm was published by V\'aclav Havel Czech mathematician in 1955  \cite{Havel1955}. Later Louis Hakimi in 1962 
\cite{Hakimi1962} independently published the same result, therefore today the theorem usually is called 
\textit{Havel-Hakimi theorem}.

\begin{theorem} \emph{(Hakimi \cite{Hakimi1962}, Havel \cite{Havel1955})} \label{th-HH} If $n \geq 1$, 
then the $n$-regular sequence $b=(b_1,\ldots,b_n)$ is $n$-graphical if and only if the sequence 
\begin{equation}
b'=(b_2 - 1, b_3 - 1, \ldots, b_{b_1} - 1, b_{b_1+1} - 1,b_{b_1+2},\ldots,b_{n-1},b_n )
\end{equation} 
is $(n - 1)$-graphical.
\end{theorem}

\begin{proof}
See \cite{Hakimi1962,Havel1955}.
\end{proof}

Let $c = (c_1,\ldots c_n)$ and $d = (d_1,\ldots,d_n)$ be $n$-bounded sequences. In 1965 Hakimi \cite{Hakimi1965} presented a 
necessary and sufficient condition for $c$ and $d$ to be the in-degree, resp. out-degree sequence of a loopless multigraph.
In 2009 this theorem was extended for directed $(a,b)$-graphs \cite{Ivanyi2009,Ivanyi2010}. In 2010 the special case 
of directed $(0,1)$-graphs was considered in \cite{ErdosMT2010,LaMar2010}.

Since the direct implementation of the theorem sorts the investigated sequence in each round, it is slow: 
the worst running time is quadratic even in that case when we use a linear time sorting algorithm.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Erd\H os-Gallai algorithm (EG) \label{subs-EG}}
In 1960 Paul Erd\H os and Tibor Gallai \cite{ErdosG1960} Hungarian mathematicians proposed a necessary and sufficient 
condition to decide, whether an $n$-regular sequence is $n$-graphical or not.

\begin{theorem} {\emph{(Erd\H os, Gallai \cite{ErdosG1960})}}
If\label{th-EG} $n \geq 1$, then the  $n$-regular sequence $b = (b_1, \ldots, b_n)$ is $n$-graphical if and only if  
\begin{equation} \sum _{i=1}^n b_i \quad \mathrm{ is \ even }  \label{eq-EG1} 
\end{equation}
and
\begin{equation}\label{eq-EG2} \sum _{i=1}^j b_i  - j(j-1) \leq \sum _{k=j+1}^n \min(j, b_k) \;\; (j=1,\ldots,n-1). 
\end{equation}
\end{theorem}

\begin{proof} See \cite{Choudum1986,ErdosG1960}.
\end{proof}

In 2010 Tripathi, Venugopalanb and West \cite{TripathiVW2010} published a constructive proof, which not only tests 
the input sequence, but for graphical inputs also constructs a corresponding simple graph. The worst running time of 
the algorithm based on their proof is $\Theta(n^3)$. 

Chungphaisan in 1974 \cite{Chungphaisan1974}, \"Ozkan in 2011 \cite{Ozkan2011} extended Erd\H os-Gallai theorem for $(0,r)$-graphs.

The following algorithm is based on Theorem \ref{th-EG}. In this paper we use the pseudocode prescribed in \cite{CormenLRS2009}.


\textit{Input.} $n$: the length of the input sequence; \\ 
$b = (b_1,\ldots,b_n):$ $n$-regular input sequence.

\textit{Output.} $L:$ logical variable ($L = \textsc{False}$ shows, that $b$ is not graphical, while if $b$ is 
graphical, then the returned value is $L = \textsc{True}$).  

\textit{Working variable.} $t$: the estimated capacity of the actual tail.

\bigskip
\noindent \textsc{Erd\H os-Gallai}$(n,b,L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_1 = b_1$              \` \textbf{//} lines 01--03: computation of the values of the vector $H$\\
\hspace{-7mm}02 \textbf{for} \= $i = 2$ \textbf{to} $n$ \\
\hspace{-7mm}03              \> $H_i = H_{i-1} + b_i$\\
\hspace{-7mm}04 \textbf{if} \= $H_n$ is odd          \` \textbf{//} lines 04--06: checking of the parity \\
\hspace{-7mm}05             \> $L =$ \textsc{False}   \` \textbf{//} lines 05--06: refuse of the nongraphical sequences\\
\hspace{-7mm}06             \> \textbf{return} $L$\\
\hspace{-7mm}07 \textbf{for} \= $i = 1$ \textbf{to} $n-1$ \` \textbf{//} lines 07--15: checking of the input\\
\hspace{-7mm}08              \> $t = 0$                   \` \textbf{//} line 08: initialization of $t$\\
\hspace{-7mm}09 \>    \textbf{for} \= $k = i + 1$ \textbf{to} $n$ \` \textbf{//} lines 09--10: computation of the tail capacity\\
\hspace{-7mm}10 \>                 \> $t = t + \min(i, b_k)$\\
\hspace{-7mm}11 \>    \textbf{if} \= $H_i - i(i - 1) > t$   \` \textbf{//} line 11: check the necessary condition\\
\hspace{-7mm}12 \>                \>  $L =$ \= \textsc{False}     \` \textbf{//} lines 12--13: the input is nongraphical\\
\hspace{-7mm}13 \>                \> \textbf{return} $L$\\
\hspace{-7mm}14 $L = \textsc{True}$                          \` \textbf{//} lines 14--15: the input is graphical\\
\hspace{-7mm}15 \textbf{return} $L$\\
\end{tabbing} 

The memory requirement of the algorithm EG is $\Theta(n)$, he running time varies between the best $\Theta(n)$ and 
the worst $\Theta(n^2)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Linear Erd\H os-Gallai algorithm (EGL)} \label{sec-linear}
In 2011 we proposed a new algorithm \textsc{Erd\H os-Gallai-Linear} (EGL) 
based on the next theorem that even in worst case needs only $\Theta (n)$ time to decide whether the input sequence is graphical.

\begin{theorem} \emph{(Iv\'anyi, Lucz \cite{IvanyiL2012Comb}, Iv\'anyi, Lucz, M\'ori, S\'ot\'er \cite{IvanyiLMS2011Acta})} 
If  $n \geq 1,$\label{th-EGL} then the $n$-regular sequence $(b_1, \ldots, b_n)$ is $n$-graphical if and only if
\begin{equation}
H_n \quad \mbox{is even}\label{eq-EGLeven}
\end{equation}
\begin{equation}
H_i \leq i(Y_i - 1) + H_n - H_{Y_i},\label{eq-EGLH}
\end{equation}
where
\begin{equation}
Y_i(b) = Y_i = 
\begin{cases}
W_i, & \mbox{ if } i \leq W_i, \\
i, & \mbox{ if } i > W_i.
\end{cases}\label{eq-EGLy}
\end{equation}
\end{theorem}
\begin{proof} See in \cite{IvanyiL2012Comb,IvanyiLMS2011Acta}.
\end{proof}

The following program is based on Theorem \ref{th-EGL}. 
It decides on arbitrary $n$-regular sequence whether it is $n$-graphical or not. 

\textit{Input}. $n$: number of vertices $(n \geq 1)$; \\
$b = (b_1, \ldots, b_n)$: $n$-regular sequence.  

\textit{Output}. $L$: logical variable, whose value is \textsc{True}, if the input is graphical, 
and it is \textsc{False}, if the input is not graphical. 

\textit{Work variables.} $i$ and $j$: cycle variables; \\
$H = (H_1,\ldots,H_n)$: $H_i$ is the cumulated degree of the first $i$ elements of the tested $b$; \\
$w$: the weight point of the actual $b_i$, that is the maximum of the indices of such elements 
of $b,$ which are not smaller than $i$; \\
$y$: the cutting point of the actual $b_i$ that is the maximum of $i$ and $w$.

\bigskip
\noindent \textsc{Erd\H os-Gallai-Linear}$(n, b, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_{1} = b_1$                                  \` \textbf{//} line 01: initialization \\
\hspace{-7mm}02 \textbf{for} \= $i=2$ \textbf{to} $n$      \` \textbf{//} line 02--03: computation of the elements of $H$\\
\hspace{-7mm}03              \> $H_{i} = H_{i-1} + b_{i}$    \` \textbf{//} line 04--06: test of the parity \\
\hspace{-7mm}04 \textbf{if} \= $H_n$ is odd\\
\hspace{-7mm}05             \> $L = \textsc{False}$\\
\hspace{-7mm}06             \>  \textbf{return}\\
\hspace{-7mm}07 $w = n$                                      \` \textbf{//} line 07: initialization of the weight point \\
\hspace{-7mm}08 \textbf{for} \= $i = 1$ \textbf{to} $n$      \` \textbf{//} lines 08--14: test of the elements of $b$\\
\hspace{-7mm}09              \> \textbf{while} \= $w > 0$ and $b_w < i$ \\
\hspace{-7mm}10              \>                \> $w = w - 1$ \\
\hspace{-7mm}11              \> $y = \max(i,w)$ \\
\hspace{-7mm}12              \> \textbf{if} \= $H_i > i(y - i) + H_n - H_y$ \\
\hspace{-7mm}13              \>             \> $L = \textsc{False}$   \` \textbf{//} lines 13--14: rejection of $b$ \\
\hspace{-7mm}14              \>             \> \textbf{return} $L$\\
\hspace{-7mm}15 $L = \textsc{True}$                         \` \textbf{//} lines 15--16: $b$ is graphical \\
\hspace{-7mm}16 \textbf{return} $L$
\end{tabbing}

The memory requirement of this algorithm is $\Theta(n)$, the time requirement changes between the best $\Theta(n)$ and the 
worst $\Theta(n^2)$.

It is worth to remark that using a linear sorting algorithm and \textsc{Erd\H os-Gallai-Linear} we can test even unsorted 
sequences in linear time.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Enumerating Erd\H os-Gallai algorithm (EGE)}\label{sec-enumerating}

A classical problem of the graph theory the enumeration of the degree sequences of different graphs-- among others 
simple graphs. For example \textit{The On-Line Encyclopedia of Integer Sequences} \cite{Sloane2011A004251} contains only 
for $n = 1, \ \ldots, \ 23$ vertices the number of degree sequences of simple graphs (the last values for $n = 20, \ 21, \ 22$ 
were set in July of 2011).

Therefore we apply the new quick EGL to get these numbers for larger number of vertices.

Our starting point was to test all regular sequences and so enumerate the graphical ones. It is easy to see that there are 
\begin{equation}
R(n) = \binom{2n - 1}{n}.\label{eq-Rn}
\end{equation}

In 1987 Ascher derived the following explicit formula for the number of $n$-even sequences $E(n)$.

\begin{lemma} \emph{(Ascher \cite{Ascher1987}, Sloane, Pfoffe \cite{SloaneP1995})} If\label{lemma-En} $n \geq 1,$ 
then the number of $n$-even sequences $E(n)$ is
\begin{equation}
E(n) = \frac{1}{2} \left ( \binom {2n -1} {n} + \binom{n - 1}{\lfloor n \rfloor} \right ).\label{eq-En}
\end{equation}
\end{lemma} 

Due to the following lemma and its consequence it is enough to test only the zerofree even sequences.

\begin{lemma}\label{lemma-GZG} \emph{(Iv\'anyi, Lucz, M\'ori, S\'ot\'er \cite{IvanyiLMS2011Acta})}
If $n \geq 2$, then the number of $n$-graphical sequences $G(n)$ can be computed from the number of 
$(n-1)$-graphical sequences $G(n - 1)$ and the number of $n$-graphical zero-free sequences $G_z(n)$: 
\begin{equation}
G(n) = G(n-1) + G_z(n).\label{eq-Gz}
\end{equation}
\end{lemma}

This assertion has the following consequence.

\begin{corollary} If\label{cor-GZG} $n \geq 1$ then
\begin{equation}
G(n) = 1 + \sum _{i=2}^n G_z(n). 
\end{equation}
\end{corollary}

Using the parallel version of EGE we computed $G_n$ till $n = 29$. These numbers can be found 
in Table \ref{fig-Gn}. 

\begin{table}
\centering
$\begin{array}{|r|rrr|}
\hline n	&	R(n)	&	E(n)	&	G(n)	\\ \hline
\textnormal{1} & \textnormal{1} & \textnormal{1} & \textnormal{1}	\\
\textnormal{2} & \textnormal{3} & \textnormal{2} & \textnormal{2}	\\
\textnormal{3} & \textnormal{10} & \textnormal{6} & \textnormal{4}	\\
\textnormal{4} & \textnormal{35} & \textnormal{19} & \textnormal{11}	\\
\textnormal{5} & \textnormal{126} & \textnormal{66} & \textnormal{31}	\\
\textnormal{6} & \textnormal{462} & \textnormal{236} & \textnormal{102}	\\
\textnormal{7} & \textnormal{1 716} & \textnormal{868} & \textnormal{342}	\\
\textnormal{8} & \textnormal{6 435} & \textnormal{3 235} & \textnormal{1 213}	\\
\textnormal{9} & \textnormal{24 310} & \textnormal{12 190} & \textnormal{4 361}	\\
\textnormal{10} & \textnormal{92 378} & \textnormal{46 252} & \textnormal{16 016}	\\
\textnormal{11} & \textnormal{352 716} & \textnormal{176 484} & \textnormal{59 348}	\\
\textnormal{12} & \textnormal{1 352 078} & \textnormal{676 270} & \textnormal{222 117}	\\
\textnormal{13} & \textnormal{5 200 300} & \textnormal{2 600 612} & \textnormal{836 315}	\\
\textnormal{14} & \textnormal{20 058 300} & \textnormal{10 030 008} & \textnormal{3 166 852}	\\
\textnormal{15} & \textnormal{77 558 760} & \textnormal{38 781 096} & \textnormal{12 042 620}	\\
\textnormal{16} & \textnormal{300 540 195} & \textnormal{150 273 315} & \textnormal{45 967 479}	\\
\textnormal{17} & \textnormal{1 166 803 110} & \textnormal{583 407 990} & \textnormal{176 005 709}	\\
\textnormal{18} & \textnormal{4 537 567 650} & \textnormal{2 268 795 980} & \textnormal{675 759 564}	\\
\textnormal{19} & \textnormal{17 672 631 900} & \textnormal{8 836 340 260} & \textnormal{2 600 672 458}	\\
\textnormal{20} & \textnormal{68 923 264 410} & \textnormal{34 461 678 394} & \textnormal{10 029 832 754}	\\
\textnormal{21} & \textnormal{269 128 937 220} & \textnormal{134 564 560 988} & \textnormal{38 753 710 486}	\\
\textnormal{22} & \textnormal{1 052 049 481 860} & \textnormal{526 024 917 288} & \textnormal{149 990 133 774}	\\
\textnormal{23} & \textnormal{4 116 715 363 800} & \textnormal{2 058 358 034 616} & \textnormal{581 393 603 996}	\\
\textnormal{24} & \textnormal{16 123 801 841 550} & \textnormal{8 061 901 596 814} & \textbf{2 256 710 139 346}	\\
\textnormal{25} & \textnormal{63 205 303 218 876} & \textnormal{31 602 652 961 516} & \textbf{8 770 547 818 956}	\\
\textnormal{26} & \textnormal{247 959 266 474 052} & \textnormal{123 979 635 837 176} & \textbf{34 125 389 919 850}	\\
\textnormal{27} & \textnormal{973 469 712 824 056} & \textnormal{486 734 861 612 328} & \textbf{132 919 443 189 544}	\\
\textnormal{28} & \textnormal{3 824 345 300 380 220} & \textnormal{1 912 172 660 219 260} & \textbf{518 232 001 761 434}	\\
\textnormal{29} & \textnormal{15 033 633 249 770 520} & \textnormal{7 516 816 644 943 559} & \textbf{2 022 337 118 015 338}	\\
\hline
\end{array} $
\begin{center}
	\caption{Number of regular, even and graphical sequences. \label{fig-Gn}}
\end{center}	
\end{table}

Due to Corollary \ref{cor-GZG} it is enough to check all of the $n$-regular zero-free sequences to compute the number 
of all $n$-graphical ones. This is a very important idea because only one fourth of the $n$-regular even sequences are 
zero-free \cite{IvanyiLMS2011Acta}, so we can safe one fourth of the work.

\begin{lemma}\label{lemma-smalltail} If $b = (b_1,\ldots,b_n)$ is a nongraphical sequence and $b_n \geq 3$, then 
the sequence $b' = (b_1,\ldots,b_{n-1},c)$ is also nongraphical for every $c$ with $0 \leq c \leq b_{n-1}$. 
\end{lemma}

Taking into account these results we have to test only one tenth of the regular sequences.

Two results due to Tripathi and Vijay \cite[Lemma 6, Theorem 7,Corollary 17]{TripathiV2003} allow to reduce the testing 
time with more than 50 percent. 

The following algorithm \textsc{Erd\H os-Gallai-Enumerating} (EGE) is an enumerative version of EGL. In this algorithm 
we use some techniques to speed up the computing process. From one side we 
we check only zero-free, even sequences. And we used lexicographical order, so most of the operations could be saved 
by updating the old values. We were updating the following values.

\begin{itemize}
	\item $H_i$ values: most of the time the only thing that is changing is the last element of the sequence $b$, 
	so it is enough to update the last $H$ values, according to the changes of the values of $b$.
	\item $C_i$ checkpoints: if we modify the $i$th element of the sequences then the values before that point remain 
	the same so all of the checkpoint before that will be the same, so we update only the first one before the $i$th 
	index and all of them after it.
	\item $W_i$ weight points: every time the checking algorithm got a sequence to check we update the weight points we use, 
	but we never start from $1$ or $n$. We use the last value we used when we checked a sequence in that index. We have 
	a distinct weight point for every $i$ index and we just shift the value to left or right.
	\item $Y_i$ cutting points:
\end{itemize}

We suppose that $n, \ b, \ H, \ c, \ C, \ W$ and $Y$ are global variables, therefore their \textbf{return} does not require 
additional time. 

Important property of EGE is that it solves in $\Theta(1)$ average time 
\begin{itemize}
\item
the generation of one zerofree even sequence;
\item
the updating of the sequence of the cumulated degrees $H$;
\item
the updating of the sequence of the checking points $C$;
\item
the updating of the sequence of the weight points $W$.
\end{itemize}

The average running time of this algorithm for a sequence is $\Theta(1)$, so the total running time of the whole program 
is $\Theta(E(n))$.

\bigskip
\noindent \textsc{Erd\H os-Gallai-Enumerating}$(n,G_z)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm} 01 \textbf{for} \= $i = 1$ \textbf{to} $n$   \` \textbf{//} lines 01--09: initialization \\
\hspace{-7mm} 02              \> $b_i = n - 1$ \\
\hspace{-7mm} 03              \> $H_i = i(n - 1)$ \\
\hspace{-7mm} 04              \> $W_i = n$ \\
\hspace{-7mm} 05              \> $y_i = n - 1$ \\
\hspace{-7mm} 06              \> $C_i = 0$ \\
\hspace{-7mm} 07 $G_z = 1$ \\
\hspace{-7mm} 08 $c = 0$\\
\hspace{-7mm} 09 $b_{n+1} = -1$ \\
\hspace{-7mm} 10 \textbf{while} \= $b_2 \geq 2$ or $b_1 \geq 3$               \` \textbf{//} line 10: last sequence was? \\
\hspace{-7mm} 11                \> if $b_n \geq 3$ \textsc{New3}$(n,b,H,c,C,W)$  \` \textbf{//} lines 11--13: generate the next sequence \\
\hspace{-7mm} 12                \> if $b_n = 2$ \textsc{New2}$(n,b,H,c,C,W)$   \\
\hspace{-7mm} 13                \> if $b_n = 1$ \textsc{New1}$(n,b,H,c,C,W)$   \\
\hspace{-7mm} 14                \> \textsc{Check}$(n,b,H,c,W)$  \` \textbf{//} line 12: checks and updates the parameters \\
\hspace{-7mm} 15                \> $G_z = G_z + L$              \` \textbf{//} line 13: increasing of $G_z$ \\    
\hspace{-7mm} 16 print $G_z$                                    \` \textbf{//} line 14: final result \\
\end{tabbing}

This algorithm uses two procedures. \textsc{New} generates a new sequences and update the key parameters, while \textsc{Check} 
decides whether the actually investigated sequence is graphical or not.

In \textsc{Check} we use condition \eqref{eq-EG1} of Erd\H os-Gallai theorem.

\bigskip
\noindent \textsc{Check}$(n,b,H,c,C,W)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{for} \= $i=1$ \textbf{to} $c$       \` \textbf{//} lines 01--07: checking in checkpoints \\
\hspace{-7mm}02              \> $y = \max{w,i}$             \` \textbf{//} line 02: computation of the actual cutting point \\ 
\hspace{-7mm}03              \> \textbf{if} \= $H_i > i(y - 1) + H_n -H_y$ \` \textbf{//} line 03--05: EG checking\\
\hspace{-7mm}04              \>             \> $L = 0$ \\                     
\hspace{-7mm}05              \>             \> \textbf{return} $L$ \\
\hspace{-7mm}06 $L = 1$                                                     \` \textbf{//} line 06--07: $b$ is graphical\\
\hspace{-7mm}07 \textbf{return} $L$
\end{tabbing}

\bigskip
\noindent \textsc{New1}$(n,b,H,c,C)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{if} \= $b_n \geq 3$  \` \textbf{//} line 01--06:  generation if $b_n = 3$ \\
\hspace{-7mm}02             \> $b_n = b_n - 2$  \\
\hspace{-7mm}03             \> $H_n = H_n - 2$ \\
\hspace{-7mm}04             \> \textbf{if} \= $b_n == b_{n-1} - 3$ \\
\hspace{-7mm}05             \>             \> $c = c + 1$ \\
\hspace{-7mm}06             \>             \> $C_c = n - 1$ \\
\hspace{-7mm}07             \> $W = ?$
\hspace{-7mm}08 \textbf{return} $H,C,W$
\end{tabbing}

\bigskip
\noindent \textsc{New2}$(n,b,H,c,C)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{if} \= $b_n == 2$              \` \textbf{//} line 08--16:  generation if $b_n = 2$ \\
\hspace{-7mm}02             \> \textbf{if} \= $b_{n} = b_{n-1} - 1$ \\
\hspace{-7mm}03             \>             \> $H_n = H_n - 1$ \\
\hspace{-7mm}04             \>             \> $c = c - 1$ \\
\hspace{-7mm}05             \> \textbf{if} \= $b_{n-1}$ is odd \\
\hspace{-7mm}06             \>             \> \textbf{if} \= $b_{n-2} = b_{n-1} + 1$ \\
\hspace{-7mm}07             \>             \>             \> $c = c - 1$ \\
\hspace{-7mm}08             \> $W = ???$ \\
\hspace{-7mm}09 \textbf{return} $H,C,W$ 
\end{tabbing}

 \textsc{New3} is similar to  \textsc{New2} although more complicated.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Parallel Erd\H os-Gallai algorithm (EGP)}\label{sec-parallel}
To use our new linear time algorithm on a bunch of series we need an algorithm that can work on a part of all series we want 
to check. From now we will use the notation $G(n)$ for the number of $n$-graphical series and $G_z(n)$ for the number 
of n-graphical zero-free series. The reason to use $z_n$ values is the following lemma.

Using our \textit{Parallel} algorithm we computed this number till $n = 29$. These number can be found 
in Table \ref{fig-Gn}.

Originally we used a server-client application consisting of two parts: server and client. The server had all the 
information to distribute jobs between client machines and collect results from them and the client had the IP address 
and the PORT of the server to ask for a job. 
To compute $G_z(n)$ value on multiple computers first we need to decompose the whole problem to smaller parts 
so called \textit{jobs}, that we could pass to them. This is one of the most critical part of the parallel algorithm: 
divide the problem into almost same sized jobs. The next equation helps us to count approximately how many sequences 
starts with a fixed head.  By knowing these numbers we can generate jobs with limited size, so every job is smaller 
than that maximum.


\bigskip
\noindent \textsc{Generate-Matrix}$(n, MaxSize)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{for} $i = n$ \textbf{downto} $2$  \` $\rhd$ Lines 01--05: filling up the matrix\\
\hspace{-7mm}02 \> \textbf{for}  $j=1$ \textbf{to} $n-1$ \\
\hspace{-7mm}03 \>	\> $M_{i, j} = {i+j-2 \choose i-1}$\\ 
\hspace{-7mm}04 \> \textbf{end} \\
\hspace{-7mm}05 \textbf{end} \\
\hspace{-7mm}06 \textbf{for} $j = n-1$ \textbf{downto} $1$ \` $\rhd$ Lines 06--08: fill up the first line in matrix \\
\hspace{-7mm}07 \> $M_{1,j} = 1$  \\ 
\hspace{-7mm}08 \textbf{end} \\
\hspace{-7mm}09 \textbf{Generate-Sequences}$(M, n, n, 1, n-1, MaxSize, 0)$ \\ \` $\rhd$ Line 09: job generation\\ 
\end{tabbing}

This algorithm give us a matrix filled up with values computed with the equation. Now, we can generate the sequences 
by read out the last row from the matrix from left to right. If a value is too big and not fit into a job, 
then we can move one line above that value and read that line from the first column until the one that was too big 
and we can continue this technique until we got size of parts we need. The next (recursive) algorithms reads out 
the last row with this method.





In the \textit{On-Line Encyclopedia of Integer Sequences} \cite{Sloane2011A004251} you can find numbers of degree-vectors 
for simple graphs, that consist of $n$ vertices, where $n$ is from $1$ to $23$. 
Originally we used a server-client application consisting of two parts: server and client. The server had all the 
information to distribute jobs between client machines and collect results from them and the client had the IP address 
and the PORT of the server to ask for a job. 

During the calculations we used more than two hundred computers and our theoretical maximal performance was over $6$ TFLOPS 
based on the processors information we found on the manufacturers home pages.
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Summary\label{sec-summary}} 

\begin{acknowledgements} The authors are indebted to Zolt\'an Kir\'aly (E\"otv\"os Lor\'and University, Faculty of Science, 
Dept. of Operation Research) for the useful continuous consultation, Antal S\'andor and his colleagues 
(E\"otv\"os Lor\'and University, Faculty of Informatics), \'Ad\'am M\'anyoki (TFM World Kereskedelmi \'es Szolg\'altat\'o Kft.) 
and Zolt\'an K\'asa (Sapientia Hungarian University of Transylvania) for their help in running of our 
timeconsuming programs. The European Union and the European Social Fund have provided financial support to the project 
under the grant agreement no. T\'AMOP 4.2.1/B-09/1/KMR-2010-0003.
\end{acknowledgements}


\begin{thebibliography}{}

\bibitem{Ascher1987} Ascher M (1987) Mu torere: an analysis of a Maori game,
Math. Mag 60(2):90--100

\bibitem{AnholzerBBK2011} Anholcer M, Babiy V, Boz\'oki S, Koczkodaj W. V (2011)
A simplified implementation of the least squares solution for pairwise comparisons matrices. 
Central Eur J Oper Res 19(4):439--444

\bibitem{BarnesS1997}  Barnes TM, Savage CD (1997) Efficient generation of graphical partitions.  
Discrete Appl Math 78:17--26

\bibitem{BozokiFK2011} Boz\'oki S, F\"ul\"op J, Koczkodaj WW (2011) An LP-based inconsistency monitoring 
of pairwise comparison matrices. Math Comp Modelling  54:789--793

\bibitem{BozokiFP2011} Boz\'oki S, F\"ul\"op J, Poesz A (2011) On pairwise comparison matrices that can be made
consistent by the modification of a few elements. Central Eur J Oper Res 19(2):157--175

\bibitem{BozokiFR2010} Boz\'oki S, F\"ul\'op J, R\'onyai L (2010) On optimal completion of incomplete 
pairwise comparison matrices. Math Comput Modelling 52:318--333

\bibitem{Choudum1986} Choudum, SA (1986) A simple proof of the Erd\H os-Gallai theorem on graph sequences. 
Bull Austral Math Soc 33:67--70

\bibitem{Chungphaisan1974} Chungphaisan, V (1974) Conditions for sequences to be $r$-graphical.  
Discrete Math. 7:31--39

\bibitem{CormenLRS2009} Cormen TH, Leiserson ChE, Rivest RL, Stein C (2009) Introduction to Algorithms (Third edition). 
The MIT Press/McGraw Hill, Cambridge/New York

\bibitem{ErdosG1960} Erd\H os P, Gallai T (1960) Graphs with prescribed degree sequence (Hungarian). Mat Lapok 11:264--274

\bibitem{ErdosMT2010} Erd\H os P, Mikl\'os I, Toroczkai Z (2010) A simple Havel-Hakimi type algorithm to realize 
graphical degree sequences of directed graphs. Electron J Combin 17:1 R66 (10 pages).

\bibitem{Frank2011} Frank A (2011) Connections in Combinatorial Optimization. Oxford University Press, Oxford

\bibitem{Hakimi1962} Hakimi SL (1962) On the realizability of a set of integers as degrees of the vertices 
of a simple graph. J SIAM Appl Math 10:496--506

\bibitem{Hakimi1965} Hakimi SL (1965) On the degrees of the vertices of a graph. F Franklin Institute 279(4)290--308
  
\bibitem{Havel1955} Havel V (1955) A remark on the existence of finite graphs (Czech). \u{C}asopis P\u{e}st Mat    
80:477--480

\bibitem{Ivanyi2009} Iv\'anyi A (2009) Reconstruction of complete interval tournaments. Acta Univ Sapientiae, 
Inform 1(1):71--88

\bibitem{Ivanyi2010} Iv\'anyi A (2010), Reconstruction of complete interval tournaments. {I}{I}. Acta Univ Sapientiae,  
Math 2(1):47--71

\bibitem{IvanyiL2012Comb} Iv\'anyi A,  Lucz L (2011) Erd\H os-Gallai test in linear time. Combinatorica (submitted).

\bibitem{IvanyiLMS2011Acta} Iv\'anyi A, Lucz L, M\'ori FT, S\'ot\'er P (2011) Quick Erd\H os-Gallai algorithms, 
Acta Univ Sapientiae, Inform 3(2):230-268
 
\bibitem{IvanyiLM2011AML} Iv\'anyi A, Lucz L, M\'ori FT (2011) Linear Erd\H os-Gallai test (Hungarian) Alk 
Mat Lapok (submitted)

\bibitem{IvanyiP2011} Iv\'anyi A, Pirzada S (2011) Comparison based ranking. In: Algorithms of Informatics  
(electronic book, ed. by A. Iv\'anyi), AnTonCom, Budapest, 1410--1450

\bibitem{Keri2011} K\'eri G. (2011) On qualitatively consistent, transitive and contradictory judgment matrices 
emerging from multiattribute decision procedures. Central Eur J Oper Res 19(2):215--224

\bibitem{KimTME2009} Kim H, Toroczkai Z, Mikl\'os I, Erd\H os PL, Sz\'ekely LA (2009)    
Degree-based graph construction. J Physics: Math Theor A 42:392--401 

\bibitem{LaMar2010} LaMar MD (2010) Algorithms for realizing degree sequences of directed graphs. 
arXiv-0906:0343ve [math.CO], 7 June 2010

\bibitem{Landau1953} Landau HG (1953) On dominance relations and the structure of animal societies. III. 
The condition for a score sequence. Bull Math Biophys 15:143--148

\bibitem{LiljerosEASA2001} Liljeros F, Edling CR, Amaral A, Stanley H, $\mbox{\AA}$berg Y (2001)  
The web of human sexual contacts. Nature 411(6840):907--908

\bibitem{LuczISP2012MaCS} Lucz L, Iv\'anyi A (2012) Testing and enumeration of football sequences,  
Abstracts of MaCS 2012, ed. by Z. Cs\"ornyei (Si\'ofok, February 9--12, 2012).

\bibitem{NarayanaB1964} Narayana TV, Bent DH (1964) Computation of the number of score sequences in round-robin tournaments. 
Canad Math Bull 7:133--136

\bibitem{NewmanB2006} Newman MEJ, Barab\'asi AL (2006)   
The Structure and Dynamics of Networks. Princeton University Press, Princeton, NJ

\bibitem{Ozkan2011} \"Ozkan S (2011) Generalization of the Erd\H os-Gallai inequality. Ars Combin 98:295--302

\bibitem{PecsySz2000} P\'ecsy G, Sz\H ucs L (2000) Parallel verification 
and enumeration of tournaments. Studia Univ Babe\c s-Bolyai, Inform XLV(2):11--26 

\bibitem{RuskeyCES1994} Ruskey F, Cohen R, Eades P, Scott A (1994)   
Alley CAT's in search of good homes. Congr Numer 102:97--110

\bibitem{Sloane2011A004251} Sloane NJA (2011) The number of degree-vectors for simple graphs. 
In: The On-Line Encyclopedia of the Integer Sequences (ed. by NJA Sloane). http://oeis.org/A004251 

\bibitem{SloaneP1995} Sloane NJA, Plouffe S (1995) The Encyclopedia of Integer Sequences. Academic Press, 1995. 

\bibitem{Temesi2011} Temesi J (2011) Pairwise comparison matrices and the error-free property of the decision maker. 
Central Eur J Oper Res 19 (2) 239--249

\bibitem{TripathiVW2010} Tripathi A, Venugopalanb S, West DB (2010)  
A short constructive proof of the Erd\H os-Gallai characterization of graphic lists. 
Discrete Math  310:833--834

\bibitem{TripathiV2003} Tripathi A, Vijay S (2003) A note on a theorem of Erd\H os \& Gallai.  
Discrete Math 265:417--420

\end{thebibliography}

\end{document}

