Algorithmic Aspects of a General Modular Decomposition Theory

Details Algorithmic Aspects of a General Modular Decomposition Theory Algorithmic Aspects of a General Modular Decomposition Theory

2006-11-04

arxiv.org/abs/cs/0611019v2

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Algorithmic Aspects of a General Modular Decomposition Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithmic Aspects of a General Modular Decomposition Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic Aspects of a General Modular Decomposition Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-76066