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
reductionstable setindependence numberstability numbermaximum independent setgraph transformationMIN algorithmMAX algorithmvertex order algorithm
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)
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
