Unifying two Graph Decompositions with Modular Decomposition

Details Unifying two Graph Decompositions with Modular Decomposition Unifying two Graph Decompositions with Modular Decomposition

2006-04-16

arxiv.org/abs/cs/0604065v3

Dans Lecture Notes in Computer Science - International Symposium on Algorithms and Computation (ISAAC, Sendai : Japon (2007)

Computer Science

Data Structures and Algorithms

Soumis \`a ISAAC 2007

Scientific paper

10.1007/978-3-540-77120-3

We introduces the umodules, a generalisation of the notion of graph module. The theory we develop captures among others undirected graphs, tournaments, digraphs, and $2-$structures. We show that, under some axioms, a unique decomposition tree exists for umodules. Polynomial-time algorithms are provided for: non-trivial umodule test, maximal umodule computation, and decomposition tree computation when the tree exists. Our results unify many known decomposition like modular and bi-join decomposition of graphs, and a new decomposition of tournaments.

Affiliated with

Also associated with

No associations

Rating

Unifying two Graph Decompositions with Modular Decomposition 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 Unifying two Graph Decompositions with Modular Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unifying two Graph Decompositions with Modular Decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-241848