Description of alpha

Home > matgraph > @graph > alpha.m

alpha

PURPOSE

[a,S] = alpha(g) --- indepencence number

SYNOPSIS

function [a,S] = alpha(g)

DESCRIPTION

 [a,S] = alpha(g) --- indepencence number
 returns a, the independence number of the graph g, and an independent set
 S of maximum cardinality.
 Note: Uses linear programming and may work slowly (if at all) on large 
 graphs.

 REQUIRES THE OPTIMIZATION TOOLBOX

CROSS-REFERENCE INFORMATION

This function calls:

• incidence_matrix incidence_matrix(g) --- return the vertex/edge incidence matrix.
• size size(g) --- returns [nv,ne] for the graph

This function is called by:

• omega [w,S] = omega(g) --- clique number

SOURCE CODE

0001 function [a,S] = alpha(g)
0002 % [a,S] = alpha(g) --- indepencence number
0003 % returns a, the independence number of the graph g, and an independent set
0004 % S of maximum cardinality.
0005 % Note: Uses linear programming and may work slowly (if at all) on large
0006 % graphs.
0007 %
0008 % REQUIRES THE OPTIMIZATION TOOLBOX
0009 
0010 [n,m] = size(g);
0011 M = incidence_matrix(g);
0012 M = double(M');
0013 
0014 c = -ones(1,n);
0015 b = ones(m,1);
0016 
0017 x = bintprog(c,M,b);
0018 
0019 a = sum(x);
0020 S = find(x)';

---

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003