...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph
【24h】

On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph

机译：在为比赛的弧线着色时，涵盖最短路径，并减小图形的直径

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

摘要

We define closed edge colorings of directed graphs, and state a conjecture about the maximum size of a tournament graph that can be arc-colored with m colors and contain no closed subgraphs. We prove special cases of this conjecture. We show that if this conjecture is correct then for any (undirected) graph with positive edge lengths and a given subset V′ of nodes, covering all the shortest paths between pairs of nodes of V ′ requires at least |V′|-1 edges. We use the latter property to produce an approximation algorithm with improved bound for minimizing the diameter or the radius of an unweighted graph by adding to it a given number of new edges.
机译：我们定义了有向图的闭合边缘着色，并提出了关于锦标赛图最大尺寸的猜想，该锦标赛图可以用m种颜色进行弧形着色，并且不包含闭合子图。我们证明了这种猜想的特殊情况。我们证明，如果这个猜想是正确的，那么对于任何具有正边长和给定节点V'的子图（无向），覆盖V'的节点对之间的所有最短路径至少需要| V'| -1边。我们使用后者的属性来生成具有改进边界的近似算法，以通过向其添加给定数量的新边来最小化未加权图的直径或半径。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号