
arXiv: 1310.1012
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.
graph algorithms, FOS: Computer and information sciences, decomposition, Discrete Mathematics (cs.DM), 2-structures, modular decomposition, [INFO] Computer Science [cs], involution modular decomposition, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Coloring of graphs and hypergraphs, Graph algorithms (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), switch cographs, Computer Science - Discrete Mathematics
graph algorithms, FOS: Computer and information sciences, decomposition, Discrete Mathematics (cs.DM), 2-structures, modular decomposition, [INFO] Computer Science [cs], involution modular decomposition, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Coloring of graphs and hypergraphs, Graph algorithms (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), switch cographs, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
