Algorithmic aspects of switch cographs
From MaRDI portal
Publication:906430
DOI10.1016/J.DAM.2015.07.008zbMATH Open1329.05277arXiv1310.1012OpenAlexW2963561518MaRDI QIDQ906430
Author name not available (Why is that?)
Publication date: 21 January 2016
Published in: (Search for Journal in Brave)
Abstract: This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structure which has a unique linear-sized decomposition tree. We derive an O(n^2) decomposition algorithm and we take advantage of the involution modular decomposition tree to state several algorithmic results. Cographs are the graphs that are totally decomposable w.r.t modular decomposition. In a similar way, we introduce the class of switch cographs, the class of graphs that are totally decomposable w.r.t involution modular decomposition. This class generalizes the class of cographs and is exactly the class of (Bull, Gem, Co-Gem, C_5)-free graphs. We use our new decomposition tool to design three practical algorithms for the maximum cut, vertex cover and vertex separator problems. The complexity of these problems was still unknown for this class of graphs. This paper also improves the complexity of the maximum clique, the maximum independant set, the chromatic number and the maximum clique cover problems by giving efficient algorithms, thanks to the decomposition tree. Eventually, we show that this class of graphs has Clique-Width at most 4 and that a Clique-Width expression can be computed in linear time.
Full work available at URL: https://arxiv.org/abs/1310.1012
No records found.
No records found.
This page was built for publication: Algorithmic aspects of switch cographs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906430)
