91. |
92. |
93. |
94. |
95. |
96. The exact weighted independent set problem in perfect graphs and related classesMartin Milanič, Jérôme Monnot, 2009, published scientific conference contribution Abstract: The exact weighted independent set (EWIS) problem consists in determining whether a given vertex-weighted graph contains an independent set of given weight. This problem is a generalization of two well-known problems, the NP-complete subset sum problem and the strongly NP-hard maximum weight independent set (MWIS) problem. Since the MWIS problem is polynomially solvable for some special graph classes, it is interesting to determine the complexity of this more general EWIS problem for such graph classes. We focus on the class of perfect graphs, which is one of the most general graph classes where the MWIS problem can be solved in polynomial time. It turns out that for certain subclasses of perfect graphs, the EWIS problem is solvable in pseudopolynomial time, while on some others it remains strongly NP-complete.In particular, we show that the EWIS problem is strongly NP-complete for bipartite graphs of maximum degree three, but solvable in pseudo-polynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes.
Keywords: graf, neodvisna množica, popolni graf, dvodelni graf
Published in RUP: 15.10.2013; Views: 2898; Downloads: 116
 Link to full text |
97. |
98. A note on domination and independence-domination numbers of graphsMartin Milanič, 2013, published scientific conference contribution Abstract: Vizing's conjecture is true for graphs ▫$G$▫ satisfying ▫$\gamma^i(G) = \gamma(G)$▫, where ▫$\gamma(G)$▫ is the domination number of a graph ▫$G$▫ and ▫$\gamma^i(G)$▫ is the independence-domination number of ▫$G$▫, that is, the maximum, over all independent sets ▫$I$▫ in ▫$G$▫, of the minimum number of vertices needed to dominate ▫$I$▫. The equality ▫$\gamma^i(G) = \gamma(G)$▫ is known to hold for all chordal graphs and for chordless cycles of length ▫$0 \pmod{3}$▫. We prove some results related to graphs for which the above equality holds. More specifically, we show that the problems of determining whether ▫$\gamma^i(G) = \gamma(G) = 2$▫ and of verifying whether ▫$\gamma^i(G) \ge 2$▫ are NP-complete, even if ▫$G$▫ is weakly chordal. We also initiate the study of the equality ▫$\gamma^i = \gamma$▫ in the context of hereditary graph classes and exhibit two infinite families of graphs for which ▫$\gamma^i < \gamma$▫.
Keywords: Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Published in RUP: 15.10.2013; Views: 3108; Downloads: 128
 Full text (300,57 KB) |
99. |
100. |
