On Fixed-Parameter Solvability of the Minimax Path Location Problem  

作　　者：Hao Lin Cheng He 

机构地区：[1]School of Science,Henan University of Technology,Zhengzhou,450001,Henan,China

出　　处：《Communications on Applied Mathematics and Computation》2023年第4期1644-1654,共11页应用数学与计算数学学报（英文）

摘　　要：The minimax path location problem is to find a path P in a graph G such that the maximum distance d_(G)(v,P)from every vertex v∈V(G)to the path P is minimized.It is a well-known NP-hard problem in network optimization.This paper studies the fixed-parameter solvability,that is,for a given graph G and an integer k,to decide whether there exists a path P in G such that max v∈V(G)d_(G)(v,P)≤k.If the answer is affirmative,then graph G is called k-path-eccentric.We show that this decision problem is NP-complete even for k=1.On the other hand,we characterize the family of 1-path-eccentric graphs,including the traceable,interval,split,permutation graphs and others.Furthermore,some polynomially solvable special graphs are discussed.

关 键 词：Discrete location Path location Fixed-parameter solvability Graph characterization Polynomial-time algorithm 

分 类 号：O15[理学—数学]