The Library
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
Tools
Lozin, Vadim V. and Milanic, Martin (2008) A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. Journal of Discrete Algorithms, Vol.6 (No.4). pp. 595-604. doi:10.1016/j.jda.2008.04.001 ISSN 1570-8667.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.jda.2008.04.001
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Journal of Discrete Algorithms | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 1570-8667 | ||||
Official Date: | December 2008 | ||||
Dates: |
|
||||
Volume: | Vol.6 | ||||
Number: | No.4 | ||||
Page Range: | pp. 595-604 | ||||
DOI: | 10.1016/j.jda.2008.04.001 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |