首页> 外文会议>Algebraic informatics >F-Rank-Width of (Edge-Colored) Graphs
【24h】

F-Rank-Width of (Edge-Colored) Graphs

机译:(边色)图的F-Rank-Width

获取原文
获取原文并翻译 | 示例

摘要

Rank-width is a complexity measure equivalent to the clique-width of undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss an extension of the notion of rank-width to all types of graphs - directed or not, with edge colors or not -, named ¥-rank-width. We extend most of the results known for the rank-width of undirected graphs to the F-rank-width of graphs: cubic-time recognition algorithm, characterisation by excluded configurations under vertex-minor and pivot-minor, and algebraic characterisation by graph operations. We also show that the rank-width of undirected graphs is a special case of F-rank-width.
机译:等级宽度是一种等效于无向图的集团宽度的复杂性度量,并且具有良好的算法和结构特性。它尤其与顶点-次要关系有关。我们讨论了将等级宽度的概念扩展到所有类型的图的形式-命名为¥ -rank-width,无论是否定向,是否带有边缘颜色。我们将无向图的秩宽的大多数已知结果扩展到图的F秩宽:立方时间识别算法,通过顶点次和枢轴次要下的排除配置进行表征以及通过图操作进行代数表征。我们还表明,无向图的秩宽度是F秩宽度的特例。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号