In a matrix-completion problem the aim is to specify the missing entries of a matrix in order to produce a matrix with particular properties. In this paper we survey results concerning matrix-completion problems where...In a matrix-completion problem the aim is to specify the missing entries of a matrix in order to produce a matrix with particular properties. In this paper we survey results concerning matrix-completion problems where we look for completions of various types for partial matrices supported on a given pattern. We see that the existence of completions of the required type often depends on the chordal properties of graphs associated with the pattern.展开更多
This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is ...This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chordal comparability graphs.展开更多
文摘In a matrix-completion problem the aim is to specify the missing entries of a matrix in order to produce a matrix with particular properties. In this paper we survey results concerning matrix-completion problems where we look for completions of various types for partial matrices supported on a given pattern. We see that the existence of completions of the required type often depends on the chordal properties of graphs associated with the pattern.
文摘This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chordal comparability graphs.
基金Supported by the Natural Science Foundation of Education Ministry of Anhui Province (No.KJ2010B138)the Foundation for the Excellent Young Talents of Anhui Province(No.2010SQRL136ZD)the Natural Science Foundation of Chuzhou University(No.2008kj013B)
基金supported by the foundation from Department of Education of Zhejiang Province (No.Y201018696)the Nature Science Foundation of Anhui Provincial Education Department(No. KJ2011B090)
基金Supported by the Natural Science Foundation of Henan Province(082300460190)Sponsored by Program for Science and Technology Innovation Talents in Universities of Henan Province(2010HASTIT043)
