Simple, linear-time modular decomposition

@misc{citeulike:2097419, abstract = {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.}, author = {Tedder, Marc and Corneil, Derek and Habib, Michel and Paul, Christophe }, citeulike-article-id = {2097419}, eprint = {0710.3901}, keywords = {algorithms, graph, order}, month = {Oct}, posted-at = {2007-12-12 09:04:11}, priority = {2}, title = {Simple, linear-time modular decomposition}, url = {http://arxiv.org/abs/0710.3901}, year = {2007} }

TY - ELEC ID - citeulike:2097419 L3 - citeulike-article-id:2097419 TI - Simple, linear-time modular decomposition N2 - 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. KW - algorithms KW - graph KW - order AU - Tedder, Marc AU - Corneil, Derek AU - Habib, Michel AU - Paul, Christophe PY - 2007/Oct/21/ UR - http://arxiv.org/abs/0710.3901 ER -