The Library
Independent sets of maximum weight in apple-free graphs
Tools
Brandstädt, Andreas, Lozin, Vadim V. and Mosca, Raffaele (2010) Independent sets of maximum weight in apple-free graphs. SIAM Journal on Discrete Mathematics, Vol.24 (No.1). pp. 239-254. doi:10.1137/090750822 ISSN 0895-4801.
PDF
WRAP_Lozin_independent_sets.pdf - Requires a PDF viewer. Download (284Kb) |
Official URL: http://dx.doi.org/10.1137/090750822
Abstract
We present the first polynomial-time algorithm to solve the maximum weight independent set problem for apple-free graphs, which is a common generalization of several important classes where the problem can be solved efficiently, such as claw-free graphs, chordal graphs, and cographs. Our solution is based on a combination of two algorithmic techniques (modular decomposition and decomposition by clique separators) and a deep combinatorial analysis of the structure of apple-free graphs. Our algorithm is robust in the sense that it does not require the input graph G to be apple-free; the algorithm either finds an independent set of maximum weight in G or reports that G is not apple-free.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Graph algorithms, Combinatorial analysis | ||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0895-4801 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Vol.24 | ||||
Number: | No.1 | ||||
Number of Pages: | 16 | ||||
Page Range: | pp. 239-254 | ||||
DOI: | 10.1137/090750822 | ||||
Status: | Peer Reviewed | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Funder: | University of Warwick. Centre for Discrete Mathematics and Its Applications |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |