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
.Net Runtime Library for Delphi 6.0.4.0
Scimbo 1.64
AnyMap JS Maps 8.4.2
GetOrgChart 2.5.3
AnyChart JS Charts and Dashboards 8.4.2
OrgChart JS 3.8.0
dbForge Compare Bundle for MySQL 8.1
dbForge Search for SQL Server 2.3
Database Workbench Pro 5.5.0
Luxand FaceSDK 7.0
SSIS Data Flow Components 1.10
Entity Developer Professional 6.3
dbForge Index Manager for SQL Server 1.9
dbForge Data Generator For MySQL 2.2
Magento Australia Post eParcel Extension 1.0
Top Code
MATLAB Support Package for Arduino (aka ArduinoIO Package) 1.0
PHP MLM Software 2.0.1
Faculty Evaluation System 1.1
Database Workbench Pro 5.5.0
Sportsbook software by BOOKIE Software 3.01
School Management Script 1.0.4
Image retrieval - Query by Example Demo 1.0
Shopping System for Shopping Carts 1.1
Billing System 1.0.1
SCHOOL MANAGEMENT SOFTWARE 1.2
WordStat 2.0
Real Time Changing Clock v1.0
GnuWin64 64
Skeletonz 1.0b
dbForge Fusion for SQL Server 1.8
Top Rated
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
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
WeBuilder 2015 13.3
PHP Digital Download Script 1.0.4
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

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

Usage
-------

[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
matrices.



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
DCA - CT - UFRN

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

Please enter text on the image