
Heuristic Algorithm for finding Maximum Independent Set 1.0 File ID: 78605 


 Heuristic Algorithm for finding Maximum Independent Set 1.0 License: Freeware File Size: 10.0 KB Downloads: 202
Submit Rating: 



Heuristic Algorithm for finding Maximum Independent Set 1.0 Description 

Description: 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 are adjacent. Given a set of vertices, the maximum independent set problem calls for 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.1e007*n^2 + 2.2e005*n + 0.00012 seconds, (see screenshot)
The algorithm has been independently developped but is similar to: Balaji, Swaminathan, Kannan, "A Simple Algorithm to Optimize Maximum 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 of neighbors of v. The SUPPORT of a vertex v in V is defined by the sum of the degree of the vertices which are adjacent to v, i.e., support(v) = s(v) = sum( deg(u) ) where u are all vertices 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 1 and x=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 set and x(i)=0 if belongs to the Minimum vertex cover.
License: Freeware Related: allvertices, Algorithm, Binary, heuristic, and is, 81e007n2 2b, adjacency matrix, adjacent, advanced modeling, Optimization, belongs, independently, binary array, break, but is, Selected, be of O/S:BSD, Linux, Solaris, Mac OS X File Size: 10.0 KB Downloads: 202


More Similar Code 

Takes as input a bipartite graph in a variation of Guido van Rossum's dictionaryoflists format, and outputs both a maximum matching (largest possible set of nonadjacent edges) and a maximum independent set (largest possible set of nonadjacent vertices). The running time in the worst case is O(E sqrt(V)) but for many graphs it runs faster due to doing fewer than the worst case number of iterations.
This implementation is based on the 1968 Murty algorithm for finding a ranked list of the best assignments for an arbitrary cost matrix.
This algorithm uses a usersupplied assignment algorithm, such as the Munkres (Hungarian) algorithm...
This is an implementation of the KnuthMorrisPratt algorithm for finding copies of a given pattern as a contiguous subsequence of a larger text. Since KMP accesses the text only sequentially, it is natural to implement it in a way that allows...
Improved algorithms for finding the roots (direct method for first order quadratic, cubic and Quartic) are used for low order equations. Fadeev algorithm for finding the characteristic polynomial is implemented to ensure high accuracy.
This function contains the well known greedy algorithm for solving Set Cover problem (ChvdodAtal, 1979), with two small modifications: * In case of more than one possible choice at a certain step, the biggest set is chosen; * Once the...
Free Split and Merge ExpectationMaximization algorithm for Multivariate Gaussian Mixtures. This algorithm is suitable to estimate mixture parameters and the number of conpounds
Usage 
[logl , M , S , P] =...
The JonkerVolgenant algorithm is much faster than the famous Hungarian algorithm for the Linear Assignment Problem (LAP). This Matlab implementation is modified from the original C++ code made by Roy Jonker, one of the inventors of the algorithm....
A simple and fast algorithm for generating doublystochasstic matrices. (matrices, where the sum of each column and each row is exactly 1). Each matrix is chosen uniformly from the space of all NxN doublystochasstic matrices.
3D reconstruction algorithm for electron cryomicroscopy Traditional single particle reconstruction methods use either the Fourier or the delta function basis to represent the particle density map. We propose a more flexible algorithm that...
Multilayer Perceptron Neural Network Model and Backpropagation Algorithm for Simulink. Multilayer Perceptron Neural Network Model and Backpropagation Algorithm for Simulink.
Marcelo Augusto Costa Fernandes DCA  CT  UFRN 
User Review for Heuristic Algorithm for finding Maximum Independent Set 
