On The Algorithmic Complexity Of Game And Decision Making Models Arising From Network Location Problems

Location theory is a significant field in combinatorial optimization. In this thesis, we consider two classes of location models arising from location problems: k-dominating set game and decision making model under the majority rule.For the k-dominating set game, we investigate two k-dominating set game models, discuss the relationship between both games and the balancedness of them, and obtain the following main results.We introduce two k-dominating set game models, and discuss the relationship between their cores; show that the balancedness of both games on a special network, we present polynomial time algorithm for computing an element of core. For decision making models, we study the complexity problems of decision solution under the majority rule, and obtain the following main results.We give the definition of decision solution, present a fast algorithm for computing a decision solution for tree network.For the existence of decision solution on general network and the number of facility to be located is considered as the input size, we discuss complexity issues for computing a decision solution.