Increasing the Maximum Capacity Path in a Network and Its Application for Improving the Connection Between Two Routers  

作　　者：Adrian M.Deaconu Javad Tayyebi 

机构地区：[1]Department of Mathematics and Computer Science,Transilvania University of Brasov,Brasov 500036,Romania [2]Department of Industrial Engineering,Birjand University of Technology,Birjand 000097,Iran

出　　处：《Tsinghua Science and Technology》2024年第3期753-765,共13页清华大学学报（自然科学版（英文版）

摘　　要：Abstract:This paper addresses the problem of improving the optimal value of the Maximum Capacity Path(MCP)through expansion in a flexible network,and minimizing the involved costs.The only condition applied to the cost functions is to be non-decreasing monotone.This is a non-restrictive condition,reflecting the reality in practice,and is considered for the first time in the literature.Moreover,the total cost of expansion is a combination of max-type cost(e.g.,for supervision)and sum-type cost(e.g.for building infrastructures,price of materials,price of labor,etc.).For this purpose,two types of strategies are combined:(l)increasing the capacity of the existing arcs,and(l)adding potential new arcs.Two different problems are introduced and solved.Both the problems have immediate applications in Internet routing infrastructure.The first one is to extend the network,so that the capacity of an McP in the modified network becomes equal to a prescribed value,therefore the cost of modifications is minimized.A strongly polynomial-time algorithm is deduced to solve this problem.The second problem is a network expansion under a budget constraint,so that the capacity of an McP is maximized.A weakly polynomial-time algorithm is presented to deal with it.In the special case when all the costs are linear,a Meggido's parametric search technique is used to develop an algorithm for solving the problem in strongly polynomial time.This new approach has a time complexity of O(n^(4)),which is better than the time complexity of O(n4 log(n)of the previously known method from literature.

关 键 词：Maximum Capacity Path(MCP) network expansion Internet routing polynomial-time algorithms 

分 类 号：TM711[电气工程—电力系统及自动化]