...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Minimal comparability completions of arbitrary graphs
【24h】

Minimal comparability completions of arbitrary graphs

机译：任意图的最小可比性完成

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

摘要

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Pi for which Pi completion of arbitrary graphs can be achieved through such a vertex incremental approach. (C) 2007 Elsevier B.V. All rights reserved.
机译：无向图的传递方向是指对其边缘的方向分配，以使这些有向边代表图的顶点之间的传递关系。并非每个图都具有传递方向，但是通过添加边可以将每个图转换为具有传递方向的图。我们研究了向任意图形中添加极少包含的一组边的问题，以使生成的图形可传递地定向。我们证明了这个问题可以在多项式时间内解决，并且给出了一个令人惊讶的简单算法。我们在该算法中使用了顶点增量方法，并且还给出了一个更一般的结果，该结果描述了图类Pi，通过这种顶点增量方法，可以完成任意图的Pi完成。 （C）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号