DIKUL - logo
E-viri
Celotno besedilo
Recenzirano
  • Maximum Weight Independent ...
    Brandstädt, Andreas; Giakoumakis, Vassilis

    Information processing letters, 01/2012, Letnik: 112, Številka: 3
    Journal Article

    The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be NP -complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying a combination of clique separator and modular decomposition, we obtain a polynomial time solution of MWIS for hole- and co-chair-free graphs (the co-chair consists of five vertices four of which form a clique minus one edge – a diamond – and the fifth has degree one and is adjacent to one of the degree two vertices of the diamond). ► The Maximum Weight Independent Set (MWIS) problem on graphs is a frequently studied problem. ► Clique separators and modular decomposition are powerful tools for solving this problem on various graph classes. ► We combine these tools for solving MWIS efficiently on hole- and co-chair-free graphs. ► In particular, we show that prime atoms of those graphs are nearly weakly chordal.