• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Undirected Distances and the Postman-Structure of Graphs (Revised)
【24h】

Undirected Distances and the Postman-Structure of Graphs (Revised)

机译：无向距离和图的邮递员结构（修订版）

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Properties of the distance function and of shortest paths in + or - 1-weighted undirected graphs are presented. These extend basic results on matchings, on the Chinese postman problem, and on plane multicommodity flows. Distances turn out to be efficient tools to generalize the matching-structure of graphs to a structure related to subgraphs having only parity constraints on their degrees, (these are called joins or postman sets). A good characterization (linear in the number of edges), of the minimum weights of paths from a fixed vertex of an undirected graph without negative circuits is obtained. This result contains the well-known minimax theorems on minimum odd joins and maximum packings of odd cuts and strengthens them by constructing a canonical maximum packing of odd cuts with favorable properties. This packing of odd cuts is characteristic for the structure of minimum odd joins. Using these, a Gallai-Edmonds type structural description of minimum odd joins is worked out.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号