Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438440 | Theoretical Computer Science | 2014 | 8 Pages |
Abstract
Graph decompositions play a crucial role in structural graph theory and in designing efficient graph algorithms. Among them, clique separator decomposition (a decomposition tree of the graph whose leaves have no clique separator (so-called atoms)) used by Tarjan for solving various optimization problems recently received much attention. In this note, we first derive the atomic structure of two subclasses of P5P5-free graphs, where P5P5 is a chordless path on five vertices. These results enable us to provide efficient solutions for the Maximum Weight Independent Set problem in these classes of graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
T. Karthick,