Publication Year Range: Last 50 years / Publisher: elsevier b.v. / Topic: 3 selected - Searchworks@Jio Institute Digital Library Search Results

Showing total 5 results

Start Over Topic computer science Topic dominating set Topic graph theory Publication Year Range Last 50 years Publisher elsevier b.v.

Author: Zhao, Yancai, Kang, Liying, and Sohn, Moo Young
Subjects: *COMPUTER algorithms, *POLYNOMIALS, *SET theory, *DOMINATING set, *GRAPH theory, *COMPUTER science
Abstract: Abstract: Let be a simple graph with vertex set and edge set . A subset is a mixed dominating set if every element is either adjacent or incident to an element of . The mixed domination problem is to find a minimum mixed dominating set of . In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs. [Copyright &y& Elsevier]
Published: 2011
Full Text: View/download PDF

Author: Khamis, Soheir M., Daoud, Sameh S., and Essa, Hanaa A.E.
Subjects: *ALGORITHMS, *DOMINATING set, *SET theory, *GRAPH theory, *TOPOLOGICAL degree, *POLYNOMIALS, *COMPUTER science, *MATHEMATICAL analysis
Abstract: Abstract: The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. [Copyright &y& Elsevier]
Published: 2009
Full Text: View/download PDF

Author: Chen, Lei, Lu, Changhong, and Zeng, Zhenbing
Subjects: *APPROXIMATION theory, *ALGORITHMS, *DOMINATING set, *GRAPH theory, *DYNAMIC programming, *COMBINATORICS, *COMPUTER science, *MATHEMATICAL analysis
Abstract: Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [Copyright &y& Elsevier]
Published: 2009
Full Text: View/download PDF

Author: Chen, Lei, Lu, Changhong, and Zeng, Zhenbing
Subjects: *DOMINATING set, *GRAPH theory, *INTEGER programming, *ALGORITHMS, *LINEAR time invariant systems, *TREE graphs, *COMPUTER science, *MATHEMATICAL analysis
Abstract: Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]
Published: 2009
Full Text: View/download PDF

Author: Pang, Chaoyi, Zhang, Rui, Zhang, Qing, and Wang, Junhu
Subjects: *GRAPHIC methods, *DOMINATING set, *DIRECTED graphs, *GRAPH theory, *SET theory, *COMPUTER engineering, *COMPUTER networks, *COMPUTER science
Abstract: Abstract: We consider the problem of incrementally computing a minimal dominating set of a directed graph after the insertion or deletion of a set of arcs. Earlier results have either focused on the study of the properties that minimum (not minimal) dominating sets preserved or lacked to investigate which update affects a minimal dominating set and in what ways. In this paper, we first show how to incrementally compute a minimal dominating set on arc insertions. We then reduce the case of computing a minimal dominating set on arc deletions to the case of insertions. Some properties on minimal dominating sets are provided to support the incremental strategy. Lastly, we give a new bound on the size of minimum dominating sets based on those results. [Copyright &y& Elsevier]
Published: 2010
Full Text: View/download PDF

Searchworks