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.
A reduction algorithm for the weighted stable set problem in claw-free graphs
NOBILI, Paolo;
2014-01-01
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
