A new heuristic algorithm to solve the maximum independent set problem
type: Item
instance of: scholarly article
title: A new heuristic algorithm to solve the maximum independent set problem
zbMATH Open document ID: 1390.05179
author: O. Ugurlu
published in: Mathematical \& Computational Applications
publication date: 2018-07-05T00:00:00Z
review text: Summary: The Maximum Independent Set Problem is a classic graph optimization NPhard problem. Given a graph \(G=(V,E)\), the independent set problem is that of finding a maximum-cardinality subset \(S\) of \(V\) such that no two vertices in \(S\) are adjacent. In this paper, the maximum independent set problem is discussed and a new heuristic algorithm is proposed to solve this problem. The performance of the algorithm has been tested on DIMACS benchmark instances and compared with the literature works. The experimental results show that the proposed approach can yield good solutions.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 6898865
zbMATH Keywords: maximum independent set problem
zbMATH Keywords: heuristics algorithms
zbMATH Keywords: optimization
zbMATH Keywords: NP-hard problems
describes a project that uses: DIMACS
MaRDI profile type: Publication
full work available at URL: mca18030495
OpenAlex ID: W2296404885
DOI: 10.3390/MCA18030495
description: scientific article; zbMATH DE number 6898865