• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Automata, languages and programming >Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees
【24h】

Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees

机译：通过消除上射和最小校正生成树的分布式校正完成分布式Matroid基础

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

摘要

This paper proposes a time-efficient distributed solution for the matroid basis completion problem. The solution is based on a technique called elimination upcast, enabling us to reduce the amount of work necessary for the upcast by relying on the special properties of ma-troids. As an application, it is shown that the algorithm can be used for correcting a minimum weight spanning tree computed for a 1)-diameter network, after k edges have changed their weight, in time O(k + 1)).
机译：本文针对拟阵基础完备问题提出了一种省时的分布式解决方案。该解决方案基于一种称为消除上冲的技术，使我们能够通过依赖于Ma-troids的特殊属性来减少上冲所需的工作量。作为应用，表明该算法可用于校正k个边缘的权重在时间O（k +1））中为1）直径网络计算的最小权重生成树。

著录项

  • 来源
  • 会议地点 Aalborg(DK);Aalborg(DK)
  • 作者

    David Peleg;

  • 作者单位

    Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 70100, Israel;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算机软件;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号