On independent vertex sets in subclasses of apple-free graphs
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-4617Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-008-9176-0
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|
|Official Date:||April 2010|
|Number of Pages:||11|
|Page Range:||pp. 383-393|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)
Downloads per month over past year