2001/01/01 by Daishin Nakamura, Akihisa Tamura · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Mathematics #Combinatorics #Cardinality (data modeling) #Graph #Discrete mathematics #Independent set #Set (abstract data type) #Computer science
paper · pdf · doi:10.15807/jorsj.44.194
openalex publication_date 2001/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
The maximum weight/cardinality stable set problem is to find a maximum weight/cardinality stable set of a given graph. It is well known that these problems for general graphs belong to the class of NP-hard. However, for several classes of graphs, e.g., for perfect graphs and claw-free graphs and so on, these problems can be solved in polynomial time. For instance, Minty (1980), Sbihi (1980) and Lovasz and Plummer (1986) have proposed polynomial time algorithm finding a maximum cardinality stable set of a claw-free graph. Moreover, it has been believed that Minty's algorithm is the unique polynomial time algorithms finding a maximum weight stable set of a daw-free graph up to date. Here we show that Minty's algorithm for the weighted version fails for some special cases, and give modifications to overcome it.