Experimental Algorithm for the Maximum Independent Set Problem - Computer Science > Data Structures and AlgorithmsReport as inadecuate




Experimental Algorithm for the Maximum Independent Set Problem - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: We develop an experimental algorithm for the exact solving of the maximumindependent set problem. The algorithm consecutively finds the maximalindependent sets of vertices in an arbitrary undirected graph such that thenext such set contains more elements than the preceding one. For this purpose,we use a technique, developed by Ford and Fulkerson for the finite partiallyordered sets, in particular, their method for partition of a poset into theminimum number of chains with finding the maximum antichain. In the process ofsolving, a special digraph is constructed, and a conjecture is formulatedconcerning properties of such digraph. This allows to offer of the solutionalgorithm. Its theoretical estimation of running time equals to is $On^{8}$,where $n$ is the number of graph vertices. The offered algorithm was tested bya program on random graphs. The testing the confirms correctness of thealgorithm.



Author: Anatoly D. Plotnikov

Source: https://arxiv.org/







Related documents