• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Representation of graphs by OBDDs
【24h】

Representation of graphs by OBDDs

机译：OBDD表示图

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

摘要

Recently, it has been shown in a series of works that the representation of graphs by Ordered Binary Decision Diagrams (OBDDs) often leads to good algorithmic behavior. However, the question for which graph classes an OBDD representation is advantageous, has not been investigated, yet. In this paper, the space requirements for the OBDD representation of certain graph classes, specifically cographs, several types of graphs with few P(4)s, unit interval graphs, interval graphs and bipartite graphs are investigated. Upper and lower bounds are proven for all these graph classes and it is shown that in most (but not all) cases a representation of the graphs by OBDDs is advantageous with respect to space requirements. (C) 2008 Elsevier B.V. All rights reserved.
机译：最近，在一系列工作中表明，用有序二进制决策图（OBDD）表示图通常会导致良好的算法行为。但是，OBDD表示对哪些图类有利的问题尚未得到研究。在本文中，研究了某些图类（特别是cograph），几种类型的图（P（4）很少），单位间隔图，间隔图和二部图的OBDD表示的空间要求。证明了所有这些图类的上限和下限，并且表明在大多数（但不是全部）情况下，用OBDD表示图对于空间需求而言是有利的。 （C）2008 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号