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
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 18.08.31.0
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
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
Report About Heuristic Algorithm for finding Maximum Independent Set 1.0
- required fields

Please enter text on the image
  



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

Back