...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
【24h】

On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

机译：关于解析树和Myhill-Nerode类型的工具，用于处理有界秩宽度的图

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

摘要

Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rank-decomposition of a graph (on contrary to the usual approach which translates a rank-decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kante[7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle.
机译：等级宽度是Oum和Seymour引入的一种结构图度量，旨在更好地处理有界集团宽度的图。我们提出了一种简单的数学框架和工具，可轻松设计直接在图的秩分解上运行的动态算法（与通常的方法相反，该方法将秩分解转换为集团宽度表达式，并可能出现指数跳跃）。参数）。该框架的主要优点是可以很好地控制对rank-width参数的运行时依赖性。我们的新方法与Courcelle和Kante [7]的工作有关，后者首先提出了所谓的双线性图乘积作为处理秩分解的更好方法的代数表达式，并与Tui Bui-Xuan的近期并行研究相联系。和Vatshelle。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号