Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
复制标题
DOI：
10.1007/978-3-540-70575-8_52
复制
发表时间：
2008-07
期刊：
影响因子：
--
通讯作者：
Marc Tedder;D. Corneil;M. Habib;C. Paul
中科院分区：
文献类型：
--
作者：
Marc Tedder;D. Corneil;M. Habib;C. Paul
模分解是算法图论中许多重要问题的基础，包括传递定向，几类图的识别，以及某些组合优化问题。因此，已经有一个驱动器走向一个实用的，线性时间算法的问题。本文假设这样一个算法，我们提出了一个线性时间模块化分解算法，在四个简单的步骤进行。这是通过将因式分解置换的概念引入早期的递归方法来实现的。唯一使用的数据结构是一个有序的树列表，四个步骤中的每一个都相当于对这些树的简单遍历。以前的算法要么非常复杂，要么采用不切实际的数据结构。
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.