In this article the Lovász–Plummer clique reduction is extended to the weighted case and used to find a maximum weight stable set in a claw-free graph GG with nn nodes in O(n2(n2+L(n)))O(n2(n2+L(n))) time, where L(n)L(n) is the complexity of finding a maximum weight augmenting path in a line graph HH with nn nodes. The best algorithm known to date to solve the latter problem is Gabow’s maximum weight matching algorithm (applied to the root graph of HH) which has a complexity of O(n2logn)O(n2logn). It follows that our algorithm can produce a maximum weight stable set in a claw-free graph in O(n4logn)O(n4logn) time.

In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with α(G)≤3 in time O(|E|log|V|). More precisely, in time O(|E|) we check whether α(G)≤3 or produce a stable set with cardinality at least 4; moreover, if α(G)≤3 we produce in time O(|E|log|V|) a maximum weight stable set of G. This improves the bound of O(|E||V|) due to Faenza, Oriolo and Stauffer.

In this paper we deal with a probabilistic extension of the minimum power multicast (MPM) problem for wireless networks. The deterministic MPM problem consists in assigning transmission powers to the nodes, so that a multihop connection can be established between a source and a given set of destination nodes and the total power required is minimized. We present an extension to the basic problem, where node failure probabilities for the transmission are explicitly considered. This model reflects the necessity of taking uncertainty into account in the availability of the hosts. The novelty of the probabilistic minimum power multicast (PMPM) problem treated in this paper consists in the minimization of the assigned transmission powers, imposing at the same time a global reliability level to the solution network. An integer linear programming formulation for the PMPM problem is presented. Furthermore, an exact algorithm based on an iterative row and column generation procedure, as well as a heuristic method are proposed. Computational experiments are finally presented.

For a graph G let α(G) and μ(G) denote respectively the cardinality of a maximum stable set and of a maximum matching of G. It is well-known that computing α(G) is NP-hard and that computing μ(G) can be done in polynomial time. In particular checking if α(G)=μ(G) is NP-complete and relies on the fact that computing α(G) is NP-hard (Mosca, Graphs Combinat 18:367–379, 2002). A well known result of Hammer et al. (SIAM J Alg Disc Math 3(4):511–522, 1982). states that the vertex-set of a graph G can be efficiently and uniquely partitioned in two subsets (possibly empty) A and B, such that G[A] has the König-Egerváry property while G[B] can be covered by pairwise disjoint edges and odd cycles: furthermore, one has α(G)=α(G[A])+α(G[B]), where computing α(G[A]) can be done in polynomial time. For that let us call essential those graphs which can be covered by pairwise disjoint edges and odd cycles (in particular computing α(G) remains NP-hard for such graphs). This paper shows that: (i) for every essential graph G, checking if α(G)=μ(G) can be done in polynomial time; (ii) essential graphs for which α(G)=μ(G) can be recognized in polynomial time and for such graph a maximum stable set can be computed in polynomial time; (iii) a new characterization of graphs which have the König-Egerváry property can be derived in that context.

In this paper we describe some results on the linear integer programming formulation of the Probabilistic Minimum Power Multicast (PMPM) problem for wireless networks. The PMPM problem consists in optimally assigning transmission powers to the nodes of a given network in order to establish a multihop connection between a source node and a set of destination nodes. The nodes are subject to failure with some probability, however the assignment should be made so that the reliability of the connection is above a given threshold level. This model reflects the necessity of taking into account the uncertainty of hosts’ availability in a telecommunication network.