• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Algorithmic aspects of a general modular decomposition theory
【24h】

Algorithmic aspects of a general modular decomposition theory

机译：一般模块化分解理论的算法方面

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A new general decomposition theory inspired by modular graph decomposition is presented. This helps in unifying modular decomposition on different structures, including (but not restricted to) graphs. Moreover, even in the case of graphs, this new notion called homogeneous modules not only captures the classical graph modules but also allows handling 2-connected components, star-cutsets, and other vertex subsets. The main result is that most of the nice algorithmic tools developed for the modular decomposition of graphs still apply efficiently on our generalisation of modules. Besides, when an essential axiom is satisfied, almost all the important properties can be retrieved. For this case, an algorithm given by Ehrenfeucht, Gabow, McConnell and Sullivan [A. Ehrenfeucht, H. Gabow, R. McConnell, S. Sullivan, An O(n(2)) Divide-and-Conquer Algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs, journal of Algorithms 16 (1994) 283-294.] is generalised and yields a very efficient solution to the associated decomposition problem.
机译：提出了一种新的受模块图分解启发的一般分解理论。这有助于在不同的结构上统一模块化分解，包括（但不限于）图。此外，即使在图形的情况下，这种称为均质模块的新概念不仅可以捕获经典图形模块，还可以处理2个连接的组件，星形切割集以及其他顶点子集。主要结果是，为图的模块分解开发的大多数不错的算法工具仍然可以有效地应用于我们对模块的概括。此外，当满足基本公理时，几乎所有重要属性都可以检索。对于这种情况，由Ehrenfeucht，Gabow，McConnell和Sullivan给出的算法[A. Ehrenfeucht，H.Gabow，R.McConnell，S.Sullivan，一种O（n（2））分治算法，用于二元结构的素树分解和图的模块化分解，《算法》杂志16（1994） [283-294。]是广义的，它为相关的分解问题提供了非常有效的解决方案。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号