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

cliqueheuristic algorithmNP-completeNP-hardpolynomial-time algorithmmaximum independent setfinite partially ordered setclass NP

Mathematics Subject Classification ID

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

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

(5)

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

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)