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
Social Media Script 1.0
ByteScout PDF Renderer SDK 9.0.0.3079
Magento Mobile App Builder 2.0.0
Binary MLM Plan 1.0.2
Review Assistant 4.0
SSIS Data Flow Components 1.8
Maulik Shah 1.0
GetOrgChart 2.4.91
ODBC Driver for SQL Azure 2.4
EntityDAC 2.0
CarMax Clone Script 1.0
Mega Menu Magento 2 2.0
Luxand FaceSDK 6.5.1
Data Puppy Lite (64-bit) 1.0
Bytescout BarCode Reader SDK 10.1.0.1778
Top Code
Wired Ekleipo 1.0
HOW TO: Use Database and ASP Sessions to Implement ASP Security
Image Edge Detection Using Ant Colony Optimization 1.0
Flash Animated OsCommerce Templates
PHP Image Resize Script 1.0
Open Source Chat Script 1.0
Restaurant Table Booking System 2.0
Online Food Ordeing System 1.0
Ping Pong Game Code Script 1.1
MLM Software ONE 1.5.46
Magento Product Designer 1.0
Kadmos OCR/ICR engine
Aspose.Barcode for Sharepoint 1.1.0.0
Extended Kalman Filter Tracking Object in 3-D 1.0
Hotel Management - Full Board Version 6.55
Top Rated
Output Messenger 1.8.0
Aliexpress Clone- Ec21 Script 1
Indiegogo Clone 3.0
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
Travel Portal Script 9.29
Magento Product Designer 1.0
OFOS - Just Eat Clone Script 1.0
PrestaShop Upload Images Module 1.2.1
Trading Software 1.2.4
Deals and Discounts Website Script 1.0.2
ADO.NET Provider for ExactTarget 1.0
Solid File System OS edition 5.1
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: 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.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: 202



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