Article ID Journal Published Year Pages File Type
438440 Theoretical Computer Science 2014 8 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,