Algorithmic Aspects of a General Modular Decomposition Theory

@misc{citeulike:1952871, abstract = {A new general decomposition theory inspired from modular graph decomposition is presented. This helps unifying modular decomposition on different structures, including (but not restricted to) graphs. Moreover, even in the case of graphs, the terminology ``module'' not only captures the classical graph modules but also allows to handle 2-connected components, star-cutsets, and other vertex subsets. The main result is that most of the nice algorithmic tools developed for modular decomposition of graphs still apply efficiently on our generalisation of modules. Besides, when an essential axiom is satisfied, almost all the important properties can be retrieved. For this case, an algorithm given by Ehrenfeucht, Gabow, McConnell and Sullivan 1994 is generalised and yields a very efficient solution to the associated decomposition problem.}, author = {Bui-Xuan, Binh-Minh and Habib, Michel and Limouzy, Vincent and De Montgolfier, Fabien }, citeulike-article-id = {1952871}, eprint = {cs/0611019}, keywords = {algorithms, graph, order, topology}, month = {Nov}, posted-at = {2007-11-21 16:31:06}, priority = {2}, title = {Algorithmic Aspects of a General Modular Decomposition Theory}, url = {http://arxiv.org/abs/cs/0611019}, year = {2007} }

TY - ELEC ID - citeulike:1952871 L3 - citeulike-article-id:1952871 TI - Algorithmic Aspects of a General Modular Decomposition Theory N2 - A new general decomposition theory inspired from modular graph decomposition is presented. This helps unifying modular decomposition on different structures, including (but not restricted to) graphs. Moreover, even in the case of graphs, the terminology ``module'' not only captures the classical graph modules but also allows to handle 2-connected components, star-cutsets, and other vertex subsets. The main result is that most of the nice algorithmic tools developed for modular decomposition of graphs still apply efficiently on our generalisation of modules. Besides, when an essential axiom is satisfied, almost all the important properties can be retrieved. For this case, an algorithm given by Ehrenfeucht, Gabow, McConnell and Sullivan 1994 is generalised and yields a very efficient solution to the associated decomposition problem. KW - algorithms KW - graph KW - order KW - topology AU - Bui-Xuan, Binh-Minh AU - Habib, Michel AU - Limouzy, Vincent AU - De Montgolfier, Fabien PY - 2007/Nov/20/ UR - http://arxiv.org/abs/cs/0611019 ER -