Extending the MAX algorithm for maximum independent set

DOI10.7151/dmgt.1811zbMath1311.05152OpenAlexW2002004410MaRDI QIDQ2344024

Christoph Brause, Ingo Schiermeyer, Ngoc C. Lê

Publication date: 11 May 2015

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

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

zbMATH Keywords

reductionstable setindependence numberstability numbermaximum independent setgraph transformationMIN algorithmMAX algorithmvertex order algorithm

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 (4)

One-three join: a graph operation and its consequences ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ An efficient local search framework for the minimum weighted vertex cover problem ⋮ MAX for \(k\)-independence in multigraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Augmenting graphs for independent sets
• On finding augmenting graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Some results on graphs without long induced paths
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Complement reducible graphs
• Lower bounds on the stability number of graphs computed in terms of degrees
• Computing independent sets in graphs with large girth
• On the use of Boolean methods for the computation of the stability number
• Robust algorithms for the stable set problem
• Minimum degree algorithms for stability number
• On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
• Stability number in subclasses of \(P_5\)-free graphs
• 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
• New sufficient conditions for \(\alpha\)-redundant vertices
• Vertex Cover: Further Observations and Further Improvements
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• A Linear Recognition Algorithm for Cographs
• Stability in circular arc graphs
• Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal
• Algorithmic Aspects of Vertex Elimination on Graphs
• Stable sets for (P_{6}, K_{2,3})-free graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A note on \(\alpha\)-redundant vertices in graphs

This page was built for publication: Extending the MAX algorithm for maximum independent set