VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Complexity results for equistable graphs and related classes
    Milanič, Martin, 1980- ; Orlin, James B., 1953- ; Rudolf, Gábor
    The class of equistable graphs is defined by the existence of a cost structureon the vertices such that the maximal stable sets are characterized by their costs. This graph class, not contained in ... any nontrivial hereditary class, has so far been studied mostly from a structural point of view; characterizations and polynomial time recognition algorithms have been obtained for special cases. We focus on complexity issues for equistable graphs and related classes. We describe a simple pseudo-polynomial-time dynamic programming algorithm to solve the maximum weight stable set problem along with the weighted independent domination problem in some classes of graphs, including equistable graphs. Our results are obtained within the wider context of Boolean optimization; corresponding hardness results are also provided. More specifically, we show that the above problems are APX-hard for equistable graphs and that it is co-NP-complete to determine whether a given cost function on the vertices of a graph defines an equistable cost structure of that graph.
    Vir: Annals of operations research. - ISSN 0254-5330 (Vol. 188, no. 1, 2011, str. 359-370)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2011
    Jezik - angleški
    COBISS.SI-ID - 1024238932
    DOI

vir: Annals of operations research. - ISSN 0254-5330 (Vol. 188, no. 1, 2011, str. 359-370)
loading ...
loading ...
loading ...

Vnos na polico