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 optimizatio...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.展开更多
The PARAMETERIZED SET PACKING problem asks, for an input consisting of a col- lection C of n finite sets with |c|≤m for any c∈C and a positive integer k, whether C contains at least k mutually disjoint sets. We give...The PARAMETERIZED SET PACKING problem asks, for an input consisting of a col- lection C of n finite sets with |c|≤m for any c∈C and a positive integer k, whether C contains at least k mutually disjoint sets. We give a fixed-parameter-tractable algorithm for this problem that runs in times O (f(k,m)+g(k,m)n), where where, bm is the minimal positive root of m-degree equation and e= =2.7182818. In particular, this gives an O (k4(5.7k)k+[k(5.7k)k+3]n) algorithm to construct mutually k disjoint sets if |c|≤3 for any c∈C.展开更多
文摘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.
基金the Main Subject Foundation of the State Council's Office of OverseasChinese Affairs under Grant 93A109. Part of the work was
文摘The PARAMETERIZED SET PACKING problem asks, for an input consisting of a col- lection C of n finite sets with |c|≤m for any c∈C and a positive integer k, whether C contains at least k mutually disjoint sets. We give a fixed-parameter-tractable algorithm for this problem that runs in times O (f(k,m)+g(k,m)n), where where, bm is the minimal positive root of m-degree equation and e= =2.7182818. In particular, this gives an O (k4(5.7k)k+[k(5.7k)k+3]n) algorithm to construct mutually k disjoint sets if |c|≤3 for any c∈C.
文摘完全p-支配集是一个著名的NP-难问题,在无线传感网络中被用于构建无线传感节点的自我保护网络.该文主要研究完全p-支配集在DG(Disk Graph)模型及其特殊模型上的参数复杂性及参数算法设计.首先证明完全p-支配集在顶点度受限的UDG(Unit Disk Graph)上仍是NP-难的.为了深入理解完全p-支配集在UDG模型上的难解性根源,利用参数化规约进一步研究了完全p-支配集在UDG上的参数复杂性.基于难解性根源的分析,最后利用树分解技术和动态规划技术,针对平面图(一种特殊DG模型)上的完全p-支配集,设计了一个时间为O((2p+2)19.1·2^(1-k)k3 n+n3)的精确算法,其中n为给定实例中的顶点个数,k为问题解的大小.
