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. ISSN 0178-4617

Full text not available from this repository.

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 > Mathematics
Journal or Publication Title:	Algorithmica
Publisher:	Springer Verlag
ISSN:	0178-4617
Date:	April 2010
Volume:	Vol.56
Number:	No.4
Number of Pages:	11
Page Range:	pp. 383-393
Identification Number:	10.1007/s00453-008-9176-0
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
URI:	http://wrap.warwick.ac.uk/id/eprint/16612

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item