• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-theoretic concepts in computer science >Directed Rank-Width and Displit Decomposition
【24h】

Directed Rank-Width and Displit Decomposition

机译：定向秩-宽度和离散分解

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

摘要

Rank-width is a graph complexity measure that has many structural properties. It is known that the rank-width of an undirected graph is the maximum over all induced prime graphs with respect to split decomposition and an undirected graph has rank-width at most 1 if and only if it is a distance-hereditary graph. We are interested in an extension of these results to directed graphs. We give several characterizations of directed graphs of rank-width 1 and we prove that the rank-width of a directed graph is the maximum over all induced prime graphs with respect to displit decomposition, a new decomposition on directed graphs.
机译：等级宽度是一种具有许多结构属性的图形复杂性度量。众所周知，就分裂分解而言，无向图的秩宽度在所有诱导素图上都是最大的，并且当且仅当它是距离遗传图时，无向图的秩宽最多为1。我们对将这些结果扩展到有向图感兴趣。我们给出了秩为1的有向图的几个特征，并证明了有向图的秩宽在所有诱导素图上相对于分解而言是最大的，这是有向图上的新分解。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号