function output=MaxCliqueRec(Gall, V, C, best, ub)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General description:
%
% This function find a maximum clique in graph recursively.
% This is a branch-and-bound algorithm. The vertex with the maximum degree
% is chosen for branching.
%
% See details in:
% O. Coudert, "Exact coloring of real-life graphs is easy", 34th Design
% Automation Conference, pp. 21 --126, June 1997.
%
% input:
%       Gall(n,n) - The global graph. If G(i,j)=1, then (i,j) is an edge.
%                   Keeping unchanged in all recursive calls.
%       V - The vertices of the subgraph being processed in the current call
%       C - The clique under construction
%       best - The largest clique found so far
%       ub - The upper bound of size of maximum clique (Obtained from
%            Dsatur coloring algorithm)
% output: 
%       output - vertices of a maximm clique
%
% Written by: Wei Wang
% Machine Learning for Signal Processing Lab
% University of Maryland, Baltimore County
% 8/21/2007
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% return C if G is empty 
if numel(V)==0
    output=C;
    return 
end

%% find upper bound for this V, if ub < best, do nothing
G=Gall(V,V);
Cols=coloring_Dsatur(G);
k=max(Cols);
ub=min(ub, length(C)+k);
if ub<=length(best)
    output=best;
    return;
end

% Find vertex of maximum degree for branching
deg=sum(G);
pos=find(deg==max(deg));
vpos=pos(1);
v=V(vpos);

%
% Branching the current subgraph
%
G1loc=find(G(vpos,:)>0);  % local indices in G
G1=V(G1loc);    % global indices in G0
Cv=union(C,v);
best = MaxCliqueRec(Gall, G1, Cv, best, ub); % find clique in neigbours of v
if ub==length(best)
    output=best;
    return;
end

V(vpos)=[]; % remove v from G, i.e., G-v
output=MaxCliqueRec(Gall, V, C, best, ub); % find clique in G-v





