首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
A total dominating set of a graph G is a subset S of nodes such that each node of G is adjacent to some node of S. We present an O(n2) time algorithm for finding a minimum cardinality total dominating set in an interval graph (one which represents intersecting intervals on the line) by reducing it to a shortest path problem on an appropriate acyclic directed network.  相似文献   

4.
5.
In the paper, it is proved that a planar graph of maximum degree Δ?7 is (Δ+1)-totally-colorable if no 3-cycle has a common vertex with a 4-cycle or no 3-cycle is adjacent to a cycle of length less than 6.  相似文献   

6.
In this paper we present unified methods to solve the minus and signed total domination problems for chordal bipartite graphs and trees in O(n2) and O(n+m) time, respectively. We also prove that the decision problem for the signed total domination problem on doubly chordal graphs is NP-complete. Note that bipartite permutation graphs, biconvex bipartite graphs, and convex bipartite graphs are subclasses of chordal bipartite graphs.  相似文献   

7.
Cayley graphs of finite cyclic group Zn are called circulant graphs and denoted by Cay(Zn,S). For Cay(Zn,S) with n|S|+1 prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets.  相似文献   

8.
骆伟忠  蔡昭权  兰远东  刘运龙 《计算机科学》2017,44(Z11):115-118, 132
完全支配集是一个著名的NP难解问题,在无线传感器网络中具有重要应用。主要研究了能降低问题规模的规约化算法设计。通过对问题结构进行深入分析并对图中顶点进行着色,得到图中顶点之间的新的组合特性,在此基础上提出一系列高效的多项式时间的局部规约规则。证明了规约规则的正确性,并通过仿真实验验证了规约规则的有效性。  相似文献   

9.
10.
11.
We show that the problem of finding a minimum dominating set in a circle graph is APX-hard: there is a constant δ>0 such that there is no (1+δ)-approximation algorithm for the minimum dominating set problem on circle graphs unless P=NP. Hence a PTAS for this problem seems unlikely. This hardness result complements the (2+?)-approximation algorithm for the problem [M. Damian, S.V. Pemmaraju, A (2+?)-approximation scheme for minimum domination on circle graphs, J. Algorithms 42 (2) (2002) 255-276].  相似文献   

12.
Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P2 with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.  相似文献   

13.
赵学锋 《计算机应用》2011,31(7):1962-1965
针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。  相似文献   

14.
We show that for a connected graph with n nodes and e edges and maximum degree at most 3, the size of the dominating set found by the greedy algorithm is at most if , if , and if .  相似文献   

15.
We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2O(k2)nO(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of Ki,j-free graphs, which exclude, for some fixed i,jN, the complete bipartite graph Ki,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of Ki,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any tN, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.  相似文献   

16.
17.
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.  相似文献   

18.
《国际计算机数学杂志》2012,89(13):2915-2924
In this article, we present a method to derive inequalities involving various domination parameters in graphs. As an application, we determine several lower bounds for these domination parameters in trees in terms of the order and the number of leaves. Finally, we characterize the classes of extremal trees.  相似文献   

19.
Due to the fast development in data communication systems and computer networks in recent years, the necessity to protect the secret data has become extremely imperative. Several methods have been proposed to protect the secret data; one of them is the secret sharing scheme. It is a method of distributing a secret K among a finite set of participants, in such a way that only predefined subset of participant is enabled to reconstruct a secret from their shares. A secret sharing scheme realizing uniform access structure described by a graph has received a considerable attention. In this scheme, each vertex represents a participant and each edge represents a minimum authorized subset. In this paper, an independent dominating set of vertices in a graph G is introduced and applied as a novel idea to construct a secret sharing scheme such that the vertices of the graph represent the participants and the dominating set of vertices in G represents the minimal authorized set. While most of the previous schemes were based on the principle of adjacent vertices, the proposed scheme is based upon the principle of non-adjacent vertices. We prove that the scheme is perfect, and the lower bound of the information rate of this new construction is improved when compared to some well-known previous constructions. We include an experiment involving security threats to demonstrate the effectiveness of the proposed scheme.  相似文献   

20.
A vertex subversion strategy of a graph G is a set of vertices X? V(G) whose closed neighbourhood is deleted from G. The survival subgraph is denoted by G/X. The vertex-neighbour-integrity of G is defined to be VNI(G)=min{|X|+τ(G/X):X? V(G)}, where τ(G/X) is the maximum order of the components of G/X. This graph parameter was introduced by Cozzens and Wu to measure the vulnerability of spy networks. Gambrell proved that the decision problem of computing the vertex-neighbour-integrity of a graph is 𝒩𝒫-complete. In this paper we evaluate the vertex-neighbour-integrity of the composition graphs of paths and cycles.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号