...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On the stable b-matching problem in multigraphs
【24h】

On the stable b-matching problem in multigraphs

机译：关于多重图中的稳定b匹配问题

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

摘要

This paper deals with the stable b-matching problem in multigraphs, called the stable multiple activities problem, SMA for short. In an SMA instance a multigraph G = (V, E), capacity b(v) and a linear order <(v) on the set of edges incident to v, for each vertex v is an element of V are given. A stable b-matching is sought, i.e. a set of edges M such that each vertex v is incident with at most b(v) edges and for each edge e is not an element of M a vertex v incident with e and b(v) distinct edges f(1),...,f(b(v)) incident to v exist in M, all of them <(v)-smaller than e. We show how to decrease the computational complexity of the SMA algorithm to run in O(vertical bar E vertical bar) time and derive some properties of stable b-matchings. (C) 2007 Elsevier B.V. All rights reserved.
机译：本文处理多图中的稳定b匹配问题，称为稳定多重活动问题，简称SMA。在SMA实例中，对于每个顶点v是V的元素，给出了多重图G =（V，E），容量b（v）和入射到v的一组边上的线性顺序<（v）。寻求稳定的b匹配，即一组边M，以使每个顶点v最多与b（v）个边入射，并且对于每个边e都不是M的元素v与e和b（v ）入射到v的不同边f（1），...，f（b（v））存在于M中，它们均小于（v）-小于e。我们展示了如何降低SMA算法在O（竖条E竖条）时间内运行的计算复杂度，并推导稳定b匹配的一些属性。 （C）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号