Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

@incollection{citeulike:3019160, 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. This paper posits such an algorithm; we present a linear-time modular decomposition algorithm that proceeds in four straightforward steps. This is achieved by introducing the notion of factorizing permutations to an earlier recursive approach. The only data structure used is an ordered list of trees, and each of the four steps amounts to simple traversals of these trees. Previous algorithms were either exceedingly complicated or resorted to impractical data-structures.}, author = {Tedder, Marc and Corneil, Derek and Habib, Michel and Paul, Christophe }, citeulike-article-id = {3019160}, doi = {http://dx.doi.org/10.1007/978-3-540-70575-8\_52}, journal = {Automata, Languages and Programming}, keywords = {algorithms, graph, order}, pages = {634--645}, posted-at = {2008-07-18 18:43:02}, priority = {2}, title = {Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations}, url = {http://dx.doi.org/10.1007/978-3-540-70575-8\_52}, year = {2008} }

TY - CHAP ID - citeulike:3019160 L3 - citeulike-article-id:3019160 TI - Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations JF - Automata, Languages and Programming SP - 634 EP - 645 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. This paper posits such an algorithm; we present a linear-time modular decomposition algorithm that proceeds in four straightforward steps. This is achieved by introducing the notion of factorizing permutations to an earlier recursive approach. The only data structure used is an ordered list of trees, and each of the four steps amounts to simple traversals of these trees. Previous algorithms were either exceedingly complicated or resorted to impractical data-structures. KW - algorithms KW - graph KW - order AU - Tedder, Marc AU - Corneil, Derek AU - Habib, Michel AU - Paul, Christophe PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-70575-8_52 ER -