Code Directory
 Visual Basic & VB.NET
New Code
Taxi App Development 7.3
RentALL-Airbnb clone script 1.8.0
VisualNEO Web 19.4.5
PHP Ecommerce Script 1.3.2
dbForge Studio for PostgreSQL 2.1
Rentonn - Airbnb clone 1.0
VisualNEO for Windows
SentiVeillance SDK Trial 7.0.191272
dbForge SQL Complete 6.1
Uber for E-Scooters 1.0
ODBC Driver for MySQL 2.4
dbForge Schema Compare for MySQL 4.4
dbForge Studio for MySQL 8.1
dbForge Query Builder for MySQL 4.4
dbForge Data Compare for MySQL 5.5
Top Code
MATLAB Support Package for Arduino (aka ArduinoIO Package) 1.0
Taxi App Development 7.3
Online Vacation Rental Booking Website Script 4.3.0
Library Management System 1.0
PHP Ecommerce Script 1.0.4
Beremiz 1.0
OptimPID: an optimal PID controller design interface 1.0
GnuWin64 64
Java-2-Pseudo 1.0
Online Book Rental System
Azizi search engine script PHP 4.1.10
Faculty Evaluation System 1.1
MLM Software ONE 1.5.46
RentALL-Airbnb clone script 1.8.0
HTML::Lint 1.21
Top Rated
Paste phpSoftPro 1.4.1
Deals and Discounts Website Script 1.0.2
ADO.NET Provider for ExactTarget 1.0
Solid File System OS edition 5.1
Classified Ad Lister 1.0
Aglowsoft SQL Query Tools 8.2
Invoice Manager by PHPJabbers 3.0
ICPennyBid Penny Auction Script 4.0
PHP Review Script 1.0
ATN Resume Finder 2.0
ATN Site Builder 3.0
Availability Booking Calendar PHP 1.0
PHP GZ Blog Script 1.1
ATN Jobs Software 4.0
ATN Mall 2.0
Heuristic Algorithm for finding Maximum Independent Set 1.0
File ID: 78605

Heuristic Algorithm for finding Maximum Independent Set 1.0
Download Heuristic Algorithm for finding Maximum Independent Set 1.0http://www.mathworks.comReport Error Link
License: Freeware
File Size: 10.0 KB
Downloads: 203
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.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 Optimize
Maximum Independent Set", Advanced Modeling and Optimization, Volume 12, Number 1, 2010

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).

"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
x=findMIS(logical([0 1; 1 0]),[2 1]) %Higher priority to node 2

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: 203

More Similar Code

Takes as input a bipartite graph in a variation of Guido van Rossum's dictionary-of-lists 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 user-supplied assignment algorithm, such as the Munkres (Hungarian) algorithm...

This is an implementation of the Knuth-Morris-Pratt 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 Expectation-Maximization algorithm for Multivariate Gaussian Mixtures. This algorithm is suitable to estimate mixture parameters and the number of conpounds


[logl , M , S , P] =...

The Jonker-Volgenant 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 doubly-stochasstic 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 doubly-stochasstic

3D reconstruction algorithm for electron cryo-microscopy
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

User Review for Heuristic Algorithm for finding Maximum Independent Set
- required fields

Please enter text on the image