Idioma:

An O(m log n) algorithm for the weighted stable set problem in claw-free graphs with [alpha](G) [less-than or equal to] 3

Nobili, Paolo ; Sassano, Antonio

Mathematical programming, 2017-07, Vol.164 (1-2), p.157 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
An O(m log n) algorithm for the weighted stable set problem in claw-free graphs with [alpha](G) [less-than or equal to] 3
Autor: Nobili, Paolo ; Sassano, Antonio
Assuntos: Algorithms ; Graph theory ; Graphs
É parte de: Mathematical programming, 2017-07, Vol.164 (1-2), p.157
Descrição: (ProQuest: ... denotes formulae and/or non-USASCII text omitted; see image) In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with ... in time ... More precisely, in time ... we check whether ... or produce a stable set with cardinality at least 4; moreover, if ... we produce in time ... a maximum weight stable set of G. This improves the bound of ... due to Faenza, Oriolo and Stauffer.
Editor: Heidelberg: Springer Nature B.V
Idioma: Inglês

Voltar para lista de resultados