The property of NP_completeness of topologic spatial reasoning problem has been proved.According to the similarity of uncertainty with topologic spatial reasoning,the problem of directional spatial reasoning should be...The property of NP_completeness of topologic spatial reasoning problem has been proved.According to the similarity of uncertainty with topologic spatial reasoning,the problem of directional spatial reasoning should be also an NP_complete problem.The proof for the property of NP_completeness in directional spatial reasoning problem is based on two important transformations.After these transformations,a spatial configuration has been constructed based on directional constraints,and the property of NP_completeness in directional spatial reasoning has been proved with the help of the consistency of the constraints in the configuration.展开更多
Let G =（V, E） be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x...Let G =（V, E） be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x） is the set of elements of V U E adjacent or incident to x. The weight of f isw（f）∑x∈VUEf（x）.The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.展开更多
文摘The property of NP_completeness of topologic spatial reasoning problem has been proved.According to the similarity of uncertainty with topologic spatial reasoning,the problem of directional spatial reasoning should be also an NP_complete problem.The proof for the property of NP_completeness in directional spatial reasoning problem is based on two important transformations.After these transformations,a spatial configuration has been constructed based on directional constraints,and the property of NP_completeness in directional spatial reasoning has been proved with the help of the consistency of the constraints in the configuration.
基金Supported by the Natural Science Foundation of Jiangsu Province(Grant No.BK20151117)the Key Scientific Research Foundation of Higher Education Institutions of Henan Province(Grant No.15B110009)
文摘Let G =（V, E） be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x） is the set of elements of V U E adjacent or incident to x. The weight of f isw（f）∑x∈VUEf（x）.The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.
