Abstract

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.

Autore Pugliese

• Nobili Paolo

Tutti gli autori

• P. Nobili , A. Sassano

Titolo volume/Rivista

DISCRETE APPLIED MATHEMATICS

Anno di pubblicazione

2014

ISSN

0166-218X

ISBN

Non Disponibile

Numero di citazioni Wos

1

Ultimo Aggiornamento Citazioni

28/04/2018

Numero di citazioni Scopus

3

Ultimo Aggiornamento Citazioni

22/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile