Home > matgraph > @graph > dom.m

dom

PURPOSE ^

[d,S] = dom(g) --- domination number of g

SYNOPSIS ^

function [d,S] = dom(g)

DESCRIPTION ^

 [d,S] = dom(g) --- domination number of g
 The domination number is the smallest size of a set of vertices S with
 the property that every vertex is either in S or else distance 1 from
 some vertex in S. 
 Returns d, the domination number, and S a smallest dominating set.
 WARNING: It is NP hard to find the domination number of a graph, so this
 will work slowly (if at all) for large graphs. 

 REQUIRES THE OPTIMIZATION TOOLBOX

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [d,S] = dom(g)
0002 % [d,S] = dom(g) --- domination number of g
0003 % The domination number is the smallest size of a set of vertices S with
0004 % the property that every vertex is either in S or else distance 1 from
0005 % some vertex in S.
0006 % Returns d, the domination number, and S a smallest dominating set.
0007 % WARNING: It is NP hard to find the domination number of a graph, so this
0008 % will work slowly (if at all) for large graphs.
0009 %
0010 % REQUIRES THE OPTIMIZATION TOOLBOX
0011 
0012 n = nv(g);
0013 A = matrix(g) + eye(n);
0014 f = ones(1,n);
0015 b = ones(n,1);
0016 [x,d] = bintprog(f,-A,-b);
0017 S = find(x);

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