On sequential heuristic methods for the maximum independent set problem

DOI10.7151/dmgt.1965zbMath1359.05093OpenAlexW2589054486MaRDI QIDQ521760

Christoph Brause, Ngoc C. Lê, Ingo Schiermeyer

Publication date: 12 April 2017

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.1965

zbMATH Keywords

heuristicmaximum independent setMAXMINvertex orderingVO

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

MAX for \(k\)-independence in multigraphs

Cites Work

• Unnamed Item
• Augmenting graphs for independent sets
• Some results on graphs without long induced paths
• Lower bounds on the stability number of graphs computed in terms of degrees
• Minimum degree algorithms for stability number
• Lower bounds on the independence number in terms of the degrees
• Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
• On the stable set problem in special \(P_{5}\)-free graphs
• Extending the MAX algorithm for maximum independent set
• New sufficient conditions for \(\alpha\)-redundant vertices
• Algorithmic Aspects of Vertex Elimination on Graphs
• The potential of greed for independence
• A note on \(\alpha\)-redundant vertices in graphs

This page was built for publication: On sequential heuristic methods for the maximum independent set problem