• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Laminar structure of ptolemaic graphs with applications
【24h】

Laminar structure of ptolemaic graphs with applications

机译：压电图的层状结构及其应用

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

摘要

Ptolemaic graphs are those satisfying the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs. It can also be seen as a natural generalization of block graphs (and hence trees). In this paper, we first state a laminar structure of cliques, which leads to its canonical tree representation. This result is a translation of gamma-acyclicity which appears in the context of relational database schemes. The tree representation gives a simple intersection model of ptolemaic graphs, and it is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time. Using the tree representation, we also give an efficient algorithm for the Hamiltonian cycle problem.
机译：托勒密图是满足任意四个顶点的托勒密不等式的图。图类与弦图和距离遗传图的交点重合。它也可以看作是框图（以及树）的自然概括。在本文中，我们首先陈述了集团的层状结构，这导致了其规范的树表示。这个结果是伽马非循环性的一种翻译，出现在关系数据库方案的上下文中。树的表示给出了一个简单的多原子图的交集模型，并且它是按照字典顺序广度优先搜索获得的理想消除顺序在线性时间内构造的。因此，可以在线性时间内解决对石油颗粒图的识别和图同构。使用树表示法，我们还给出了哈密顿循环问题的有效算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号