格的反软理想

首先给出了格的反软理想新概念,证明2个反软理想分别在软集的限制并和"或"运算下仍然是反软理想.其次,利用软集的反对偶给出反软理想的等价刻画.再次,利用软集的反扩张原理给出反软理想在同态映射下反像与原像的性质.最后,在全体反软理想组成的集合H上,引入链条件并讨论H是阿丁的或诺特的充要条件.     

符号混合控制问题的某些NP-完全性结果

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:V∪E→ {-1, 1} such that ∑_(y∈N_m(x)∪{x})f(y)≥ 1for every element x∈V∪E, where N_m(x) is the set of elements of V∪E adjacent or incident to x. The weight of f is w(f) =∑_(x∈V∪E)f(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.