Heuristic algorithm for finding the maximum independent set

DOI10.1007/S10559-012-9448-1MaRDI QIDQ2452735zbMATH OpenOpenAlexFDO

Authors Anatoly D. Plotnikov

Publication date 5 June 2014

Published in Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10559-012-9448-1

zbMATH Keywords

class NPcliquefinite partially ordered setheuristic algorithmmaximum independent setNP-completeNP-hardpolynomial-time algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A new heuristic algorithm to solve the maximum independent set problem
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Algorithms for maximum independent sets
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• A simple algorithm to optimize maximum

Cited in

(6)

• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• A new heuristic algorithm to solve the maximum independent set problem
• A simple algorithm to optimize maximum
• scientific article; zbMATH DE number 20942 (Why is no real title available?)
• On sequential heuristic methods for the maximum independent set problem
• The cardinality of the collection of maximum independent sets of a functional graph

This page was built for publication: Heuristic algorithm for finding the maximum independent set

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