Homogeneity vs. Adjacency: generalising some graph decomposition algorithms

Details Homogeneity vs. Adjacency: generalising some graph decomposition algorithms Homogeneity vs. Adjacency: generalising some graph decomposition algorithms

2006-03-13

arxiv.org/abs/cs/0603048v1

Graph-Theoretic Concepts in Computer Science Springer (Ed.) (22/06/2006) 278-288

Computer Science

Data Structures and Algorithms

soumis \`{a} WG 2006

Scientific paper

10.1007/11917496\_25

In this paper, a new general decomposition theory inspired from modular graph decomposition is presented. Our main result shows that, within this general theory, most of the nice algorithmic tools developed for modular decomposition are still efficient. This theory not only unifies the usual modular decomposition generalisations such as modular decomposition of directed graphs or decomposition of 2-structures, but also star cutsets and bimodular decomposition. Our general framework provides a decomposition algorithm which improves the best known algorithms for bimodular decomposition.

Affiliated with

Also associated with

No associations

Rating

Homogeneity vs. Adjacency: generalising some graph decomposition algorithms 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 Homogeneity vs. Adjacency: generalising some graph decomposition algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Homogeneity vs. Adjacency: generalising some graph decomposition algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-69395