DIMACS TR: 2005-38
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
Authors: Vadim V. Lozin and Martin Milanic
ABSTRACT
The class of fork-free graphs is an extension of claw-free graphs
and their subclass of line graphs. The first polynomial-time
solution to the maximum weight independent set problem in the
class of line graphs, which is equivalent to the maximum matching
problem in general graphs, has been proposed by Edmonds in 1965
and then extended to the entire class of claw-free graphs by Minty
in 1980. Recently, Alekseev proposed a solution for the larger
class of fork-free graphs, but only for the unweighted version of
the problem, i.e., finding an independent set of maximum
cardinality. In the present paper, we describe the first
polynomial-time algorithm to solve the problem for weighted
fork-free graphs.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-38.ps.gz
DIMACS Home Page