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: This function is called by:

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