...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Clique tree generalization and new subclasses of chordal graphs
【24h】

Clique tree generalization and new subclasses of chordal graphs

机译：派生树泛化和弦图的新子类

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

摘要

The notion of a clique tree plays a central role in obtaining an intersection graph representation of a chordal graph. In this paper, we introduce a new structure called the reduced clique hypergraph of a chordal graph. Unlike a clique tree, the reduced clique hypergraph is a unique structure associated with a chordal graph. We show that all clique trees of a chordal graph can be obtained from the reduced clique hypergraph; thus the reduced clique hypergraph can be thought of as a generalization of the notion of a clique tree. We then link the reduced clique hypergraph notion to minimal vertex separators of chordal graphy by proving a structure theorem which shows that the edges of the reduced clique hypergraph are in one-one correspondence with the minimal vertex separators. We also show that a closed-form formula for the number of clique trees of a chordal graph can be derived using these results. Using an algorithmic characterization of minimal vertex separators, we obtain efficient algorithms to compute the reduced clique hypergraph and to count the number of clique trees of a chordal graph. Finally, guided by the reduced clique hypergraph structure we propose a few new subclasses of chordal graphs and relate them to each other and the existing subclasses.
机译：在获得和弦图的相交图表示中，集团树的概念起着中心作用。在本文中，我们介绍了一种新的结构，称为弦图的简化派系超图。与集团树不同，简化的集团超图是与弦图关联的独特结构。我们表明，可以从简化的集团超图获得弦图的所有集团树;因此，简化的集团超图可以被认为是集团树概念的概括。然后，通过证明一个结构定理，该简化定理超图概念与弦顶点图的最小顶点分隔符相关联，该结构定理表明简化后的集团超图的边缘与最小顶点分隔符一一对应。我们还表明，可以使用这些结果来得出弦图的集团树数的闭式公式。使用最小顶点分隔符的算法特征，我们获得了有效的算法来计算简化的集团超图并计算弦图的集团树数。最后，在简化的集团超图结构的指导下，我们提出了弦图的一些新子类，并将它们彼此关联以及与现有子类相关联。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号