Simple, linear-time modular decomposition

Details Simple, linear-time modular decomposition Simple, linear-time modular decomposition

2007-10-21

arxiv.org/abs/0710.3901v2

Computer Science

Discrete Mathematics

The paper has been entirely rewritten and repositioned to improve exposition and the detail provided in this extended abstract

Scientific paper

Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. Despite considerable effort, such an algorithm has remained elusive. The linear-time algorithms to date are impractical and of mainly theoretical interest. In this paper we present the first simple, linear-time algorithm to compute the modular decomposition tree of an undirected graph. The breakthrough comes by combining the best elements of two different approaches to the problem.

Affiliated with

Also associated with

No associations

Rating

Simple, linear-time 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 Simple, linear-time modular decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple, linear-time modular decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-210355