# 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.
ISSN 0895-4801

PDF
WRAP_Lozin_independent_sets.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 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 > 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 |

Volume: | Vol.24 |

Number: | No.1 |

Number of Pages: | 16 |

Page Range: | pp. 239-254 |

Identification Number: | 10.1137/090750822 |

Status: | Peer Reviewed |

Access rights to Published version: | Open Access |

Funder: | University of Warwick. Centre for Discrete Mathematics and Its Applications |

References: | [1] C. Berge, Two theorems in graph theory, Proc. Nat. Acad. Sci. USA, 43 (1957), pp. 842–844. |

URI: | http://wrap.warwick.ac.uk/id/eprint/3314 |

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

### Actions (login required)

View Item |

### Downloads

Downloads per month over past year