Algebraic Operations on PQ Trees and Modular Decomposition Trees
Algebraic Operations on PQ Trees and Modular Decomposition Trees
复制标题
PQ 树和模分解树的代数运算
DOI：
10.1007/11604686_37
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
F. D. Montgolfier
中科院分区：
文献类型：
--
作者：
R. McConnell;F. D. Montgolfier
部分集合族是可以相当大的集合族，但具有树形式的紧凑递归表示。这棵树是PQ树、图的模分解、布尔函数的某些分解以及各种其他组合结构上出现的分解的常见推广。我们描述自然运营商的部分集家庭，给代数身份操纵他们，并描述有效的算法来评估他们。我们使用这些结果，以获得新的时间界限找到一组排列的公共区间，找到模块化分解的边着色图（也称为两个结构），找到PQ树的矩阵时，一个召唤的安排，并找到模块化分解的置换图时，其置换实现。
Partitive set families are families of sets that can be quite large, but have a compact, recursive representation in the form of a tree. This tree is a common generalization of PQ trees, the modular decomposition of graphs, certain decompositions of boolean functions, and decompositions that arise on a variety of other combinatorial structures. We describe natural operators on partitive set families, give algebraic identities for manipulating them, and describe efficient algorithms for evaluating them. We use these results to obtain new time bounds for finding the common intervals of a set of permutations, finding the modular decomposition of an edge-colored graph (also known as a two-structure), finding the PQ tree of a matrix when a consecutive-ones arrangement is given, and finding the modular decomposition of a permutation graph when its permutation realizer is given.