Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
From MaRDI portal
Publication:1849924
DOI10.1016/S0012-365X(02)00571-XzbMath1066.68096MaRDI QIDQ1849924
Zdeněk Ryjáček, Jochen Harant, Ingo Schiermeyer
Publication date: 2 December 2002
Published in: Discrete Mathematics (Search for Journal in Brave)
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
Minimum degree algorithms for stability number ⋮ A sequential elimination algorithm for computing bounds on the clique number of a graph ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ New potential functions for greedy independence and coloring ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ Extending the MAX algorithm for maximum independent set
This page was built for publication: Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
