A new heuristic algorithm to solve the maximum independent set problem

DOI10.3390/MCA18030495MaRDI QIDQ1649282zbMATH OpenOpenAlexFDO

Authors O. Ugurlu

Publication date 5 July 2018

Published in Mathematical \& Computational Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/mca18030495

zbMATH Keywords

optimizationNP-hard problemsmaximum independent set problemheuristics algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Abstract computational complexity for mathematical programming problems (90C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A simple algorithm to optimize maximum
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• A hybrid iterated local search heuristic for the maximum weight independent set problem
• Heuristic algorithm for finding the maximum independent set
• An unconstrained binary quadratic programming for the maximum independent set problem

Cited in

(20)

• Solving the set packing problem via a maximum weighted independent set heuristic
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• A novel evolutionary formulation of the maximum independent set problem
• Simple and fast surrogate constraint heuristics for the maximum independent set problem
• New properties of maximum independent set problem solution truncation rules or redundant branches
• Maximum independent sets and supervised learning
• Heuristic algorithm for finding the maximum independent set
• An elitist genetic algorithm for the maximum independent set problem.
• A hybrid iterated local search heuristic for the maximum weight independent set problem
• New instances for maximum weight independent set from a vehicle routing application
• Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP
• A genetic algorithm for the maximum 2-packing set problem
• A simple algorithm to optimize maximum
• Algorithms for the generalized independent set problem based on a quadratic optimization approach
• Genetic algorithmic approach to find the maximum weight independent set of a graph
• An independent set approach for the communication network of the GPS III system
• A branch-and-price approach for the maximum weight independent set problem
• scientific article; zbMATH DE number 4064507 (Why is no real title available?)
• An unconstrained binary quadratic programming for the maximum independent set problem
• Using critical sets to solve the maximum independent set problem

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: A new heuristic algorithm to solve the maximum independent set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1649282)