The Library
Independent sets of maximum weight in apple-free graphs
Tools
Brandstädt, Andreas, Klembt, Tilo, Lozin, Vadim V. and Mosca, Raffaele (2008) Independent sets of maximum weight in apple-free graphs. In: 19th international symposium, ISAAC 2008, Gold Coast, Australia, 15-17 Dec 2008. Published in: Lecture Notes in Computer Science, Vol.5369 pp. 848-858. doi:10.1007/978-3-540-92182-0_74 ISSN 0302-9743.
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.1007/978-3-540-92182-0_74
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: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||
Publisher: | Springer | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Algorithms and Computation | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.5369 | ||||
Page Range: | pp. 848-858 | ||||
DOI: | 10.1007/978-3-540-92182-0_74 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 19th international symposium, ISAAC 2008 | ||||
Type of Event: | Conference | ||||
Location of Event: | Gold Coast, Australia | ||||
Date(s) of Event: | 15-17 Dec 2008 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |