Search
Code Directory
ASP
ASP.NET
C/C++
CFML
CGI/PERL
Delphi
Development
Flash
HTML
Java
JavaScript
Pascal
PHP
Python
SQL
Tools
Visual Basic & VB.NET
XML
New Code
 Code Review Bundle 1.0 Magento Delivery Date Scheduler 1.0 Devart Excel Add-ins 1.8 Faculty Evaluation System 1.1 dbForge Studio for PostgreSQL 2.0 Yelp Script - Yelp Clone 1.3 Database Workbench Pro 5.4.6 Extensibility Studio 3.0 Bytescout Spreadsheet SDK 3.0.0.1699 Magento 2 Admin Mobile App 1.0 Data Compare for MySQL 5.3 ODBC Driver for Zoho CRM 1.3 ODBC Driver for SugarCRM 1.3 Bytescout PDF To HTML SDK 9.0.0.3079 Azizi search engine script PHP 4.1.10
Top Code
 Output Messenger 1.8.0 Aliexpress Clone- Ec21 Script 1 Indiegogo Clone 3.0 Advanced MLM Software 1.2 Online Food Ordeing System 1.0 PHP Image Resize Script 1.0 Best Spotify Clone 1.0 Get Random Record Based on Weight 1.0.0 PHP Point of sale 10.0 Travel Portal Script 9.29 Excel Add-in for Bigcommerce 1.6 Magento Product Designer 1.0 OFOS - Just Eat Clone Script 1.0 PrestaShop Upload Images Module 1.2.1 Trading Software 1.2.4
Report About Heuristic Algorithm for finding Maximum Independent Set 1.0

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

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:
"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.

Back