• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Euro-Par Parallel Processing Conference; 20050830-0902; Lisbon(PT) >Efficient Truthful Mechanisms for the Single-Source Shortest Paths Tree Problem
【24h】

Efficient Truthful Mechanisms for the Single-Source Shortest Paths Tree Problem

机译：单源最短路径树问题的有效真实机制

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

摘要

Let a communication network be modelled by an undirected graph G = (V, E) of n nodes and m edges, and assume that each edge is controlled by a selfish agent. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most used structures in communication networks, i.e., the single-source shortest paths tree. More precisely, we will show that under various realistic agents' behavior scenarios, it can be guaranteed not only the existence, but also the efficiency (in terms of running time complexity) of such mechanisms. In particular, for the fundamental case in which the problem is utilitarian, we will show that a truthful mechanism can be computed in O(mn log α(m,n)) time, where α(m,n) is the classic inverse of the Ack-ermann's function.
机译：让通信网络由n个节点和m个边的无向图G =（V，E）建模，并假定每个边都由自私代理控制。在本文中，我们分析了设计一种真实机制来计算通信网络中最常用的结构之一（即单源最短路径树）的问题。更确切地说，我们将证明在各种现实的代理行为场景下，不仅可以保证这种机制的存在，而且可以保证这种机制的效率（就运行时间复杂度而言）。特别是，对于问题是功利主义的基本情况，我们将证明可以在O（mn logα（m，n））时间内计算出真实的机制，其中α（m，n）是阿克尔曼函数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号