Cost allocation for steiner trees
作者:
N. Megiddo,
期刊:
Networks
(WILEY Available online 1978)
卷期:
Volume 8,
issue 1
页码: 1-6
ISSN:0028-3045
年代: 1978
DOI:10.1002/net.3230080104
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractA set of points, called consumers, and another point called central supplier, are located in a Euclidean plane. The cost of constructing a connection between two points is proportional to the distance between them. The minimum cost required for connecting all the consumers to the supplier is given by a minimal Steiner tree. An example is given in which for every allocation of the total cost of the tree to the consumers, a coalition of consumers exists, which is charged more than the cost required for connecting its members to the central supplier.
点击下载:
PDF
(280KB)
返 回