VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Algorithmic developments and complexity results for finding maximum and exact independent sets in graphs [Elektronski vir] : dissertation
    Milanič, Martin, 1980-
    We consider the maximum independent set and maximum weight independent set problems in graphs. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, that is, ... in graph classes de.ned by a set F of forbidden induced subgraphs. We describe a condition on the set F, which guarantees that the maximum independent set problem remains NP-hard in the class of F-free graphs. The same hardness result remains valid even under the additional restriction that the graphs are planar and of maximum degree atmost three. We exhibit several cases where the condition is violated, and the problem admits a polynomial-time solution. More speci.cally, we present polynomial-time algorithms for the maximum independent set problem in: two graph classes that properly contain claw-free graphs (thus generalizing the classical result for claw-free graphs); various subclasses of planar and more general graphs; weighted graphs in certain subclasses of graphs of bounded vertex degree. ii Our algorithms are based on various approaches. In particular, we develop an extension of the method of .nding augmenting graphs.We also make extensive use of some other well-known graph decompositions. We also introduce and study the exact version of the problem, where, instead of .nding an independent set of maximum weight, the goal is to .nd an independent set of given weight. Determining the computational complexity of this problem for line graphs, or for line graphs of bipartite graphs would resolve long standing open problems. Here, we show that: The exact weighted independent set problem is strongly NP-complete for cubic bipartite graphs. The problem is solvable in pseudo-polynomial time for any of the following graph classes: mK2-free graphs, interval graphs and their generalizations k-thin graphs, circle graphs, chordal graphs, AT-free graphs, (claw, net)-free graphs, distance-hereditary graphs, and graphs of bounded tree- or clique-width. Finally, we show how modular decomposition can be applied to the exact weighted independent set problem. As a corollary, we obtain pseudo-polynomial solutions for the problem in certain subclasses of P5-free and fork-free graphs.
    Vrsta gradiva - disertacija ; neleposlovje za odrasle
    Založništvo in izdelava - New Brunswick : Rutgers University Press, 2007
    Jezik - slovenski
    COBISS.SI-ID - 2125797

    Povezava(-e):

    http://mss3.libraries.rutgers.edu/dlr/TMP/rutgers-lib_21317-PDF-1.pdf

Vnos na polico