|
findMIS is an heuristic algorithm for solving Maximum Independent Set problem (MIS).An independent set of a graph is a subset of vertices in which no two vertices areadjacent. Given a set of vertices, the maximum independent set problem callsfor finding the independent set of maximum cardinality.Algorithm run in O(n^2) time, where n is the number of vertices (worst case).Experimentally: time = 8.1e-007*n^2 + 2.2e-005*n + 0.00012 seconds, (see screenshot)The algorithm has been independently developped but is similar to:Balaji, Swaminathan, Kannan, "A Simple Algorithm to OptimizeMaximum Independent Set", Advanced Modeling and Optimization, Volume 12, Number 1, 2010 Notation:The neighborhood of v is defined by N(v) ={u in V such that u is adjacent to v}The DEGREE of a vertex v in V, denoted by deg(v) and is defined by the number ofneighbors of v.The SUPPORT of a vertex v in V is defined by the sum of the degree of the verticeswhich are adjacent to v, i.e., support(v) = s(v) = sum( deg(u) ) where u are allvertices in N(v). INPUTS:"AD" is the adjacency matrix. It must be of logical values!"priority" is used to break the ties (parity) situations that occur when more than one maximum independent set can be selected. Consider for example the trivial case of two nodes connected by one edge: there are two possible maximum independent sets. By using priority you can decide which vertex has to selected first. Try for example:x=findMIS(logical([0 1; 1 0]),[1 2]) %Higher priority to node 1andx=findMIS(logical([0 1; 1 0]),[2 1]) %Higher priority to node 2 OUTPUTS:x is an binary array where x(i)=1 if vertex i belongs to the Maximum independent setand x(i)=0 if belongs to the Minimum vertex cover.
| Requirements: |
No special requirements
|
| Platforms: |
Matlab |
| Keyword: |
81e007n2 2b, Adjacency Matrix, Adjacent, Advanced Modeling, Algorithm, Allvertices, And Is, Be Of, Belongs, Binary, Binary Array, Break, But Is, Heuristic, Independently, Optimization, Selected |
| Users rating: |
0/10 |
|
Windows Software
Albina Merfyn - I find this to be really easy to use. I can...
