Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872602 | Discrete Applied Mathematics | 2012 | 8 Pages |
Abstract
Clique separator decomposition, introduced by Whitesides and Tarjan, is one of the most important graph decompositions. A hole is a chordless cycle with at least five vertices. A paraglider is a graph with five vertices a,b,c,d,e and edges ab,ac,bc,bd,cd,ae,de. We show that every (hole, paraglider)-free graph admits a clique separator decomposition into graphs of three very specific types. This yields efficient algorithms for various optimization problems in this class of graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andreas Brandstädt, Vassilis Giakoumakis, Frédéric Maffray,