The Library
On independent vertex sets in subclasses of apple-free graphs
Tools
Brandstaedt, Andreas, Klembt, Tilo, Lozin, Vadim V. and Mosca, Raffaele (2010) On independent vertex sets in subclasses of apple-free graphs. Algorithmica, Vol.56 (No.4). pp. 383-393. doi:10.1007/s00453-008-9176-0 ISSN 0178-4617.
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/s00453-008-9176-0
Abstract
In a finite undirected graph, an apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one of the cycle vertices. A graph is apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs, claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination of clique separators with modular decomposition.
Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class; the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Algorithmica | ||||
Publisher: | Springer Verlag | ||||
ISSN: | 0178-4617 | ||||
Official Date: | April 2010 | ||||
Dates: |
|
||||
Volume: | Vol.56 | ||||
Number: | No.4 | ||||
Number of Pages: | 11 | ||||
Page Range: | pp. 383-393 | ||||
DOI: | 10.1007/s00453-008-9176-0 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
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 |