[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
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)';