DIKUL - logo
E-viri
Recenzirano Odprti dostop
  • Maximum weight independent ...
    Brandstädt, Andreas; Mosca, Raffaele

    Theoretical computer science, 07/2021, Letnik: 878-879
    Journal Article

    The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity for Pk-free graphs, k≥7, is an open problem. In 7, it is shown that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This result is extended by Maffray and Pastor 22 showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for (S1,2,3,bull)-free graphs. In this paper, using a similar approach as in 7, we show that MWIS can be solved in polynomial time for (S1,2,4,triangle)-free graphs which generalizes the result for (P7,triangle)-free graphs.