首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
Given a graph G=(V,E) with node weight w:VR + and a subset SV, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NPDTIME(n O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs. As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs.  相似文献   

2.
Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset SV of minimal size such that every vertex in VS is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.  相似文献   

3.
Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences by optimizing over possible insertions, deletions and substitutions. However, other evolutionary events can be observed, such as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to move operations is NP-complete. Previous work has shown that an extension restricted to non-overlapping inversions can be solved in O(n 3) with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can be solved in O(n 5) for general scoring schemes, O(n 4log n) for concave scoring schemes and O(n 4) for restricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping moves is provided. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 151–164.  相似文献   

4.
Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a k -distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ p k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.  相似文献   

5.
We consider dynamic routing of broadcast connections in WDM optical networks. Given the current network state, we want to find a minimum set of network nodes S such that a broadcast routing using only the nodes in S as wavelength conversion nodes can be found. This ensures that the average conversion delay from the source to all destinations is minimized. We refer to the problem as Broadcast Conversion Node Selection (BCNS) problem. We prove that BCNS has no polynomial-time approximation with performance ratio ln n for < 1 unless NPDTIME(nO(log log n)) where n is the number of vertices in the input graph. We present a greedy approximation algorithm for BCNS that achieves approximation ratio 2+ln n. Simulation results show that the algorithm performs very well in practice, obtaining optimal solutions in most of the cases.  相似文献   

6.
We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent all loyal users. When 1−p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1−p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal tree using dynamic programming algorithm in O(nK+K 4) time where K=min {4(log (1−p)−1)−1,n} and n is the number of normal users.  相似文献   

7.
We present a polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise. The Q-Ising, one of the generalized models of the Ising, arose in the context of Bayesian image restoration in statistical mechanics. We study the distribution of Q-Ising on a two-dimensional square lattice over n vertices, that is, we deal with a discrete state space {1,…,Q} n for a positive integer Q. Employing the Q-Ising (having a parameter β) as a prior distribution, and assuming a Gaussian noise (having another parameter α), a posterior is obtained from the Bayes’ formula. Furthermore, we generalize it: the distribution of noise is not necessarily a Gaussian, but any vertex-independent noise. We first present a Gibbs sampler from our posterior, and also present a perfect sampler by defining a coupling via a monotone update function. Then, we show O(nlog n) mixing time of the Gibbs sampler for the generalized model under a condition that β is sufficiently small (whatever the distribution of noise is). In case of a Gaussian, we obtain another more natural condition for rapid mixing that α is sufficiently larger than β. Thereby, we show that the expected running time of our sampler is O(nlog n).  相似文献   

8.
We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data-streaming model. To decide if the LIS of a given stream of elements drawn from an alphabet αbet has length at least k, we discuss a one-pass algorithm using O(k log αbetsize) space, with update time either O(log k) or O(log log αbetsize); for αbetsize = O(1), we can achieve O(log k) space and constant-time updates. We also prove a lower bound of Ω(k) on the space requirement for this problem for general alphabets αbet, even when the input stream is a permutation of αbet. For finding the actual LIS, we give a ⌈log (1 + 1/ɛ)-pass algorithm using O(k1+ɛlog αbetsize) space, for any ɛ > 0. For LCS, there is a trivial Θ(1)-approximate O(log n)-space streaming algorithm when αbetsize = O(1). For general alphabets αbet, the problem is much harder. We prove several lower bounds on the LCS problem, of which the strongest is the following: it is necessary to use Ω(n2) space to approximate the LCS of two n-element streams to within a factor of ρ, even if the streams are permutations of each other. A preliminary version of this paper appears in the Proceedings of the 11th International Computing and Combinatorics Conference (COCOON'05), August 2005, pp. 263–272.  相似文献   

9.
Rocchio’s similarity-based relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio’s algorithm often uses a fixed query updating factor. When this is the case, we strengthen the linear Ω(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61–86, 2002) and prove that Rocchio’s algorithm makes Ω(k(nk)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1} n , when the inner product similarity measure is used. A quadratic lower bound is obtained when k is linearly proportional to n. We also prove an O(k(nk)3) upper bound for Rocchio’s algorithm with the inner product similarity measure in searching for such a collection of documents with a constant query updating factor and a zero classification threshold.  相似文献   

10.
In this paper, we studied the MINimum-d-Disjunct Submatrix (MIN-d-DS), which can be used to select the minimum number of non-unique probes for viruses identification. We prove that MIN-d-DS is NP-hard for any fixed d. Using d-disjunct matrix, we present an O(log k)-approximation algorithm where k is an upper bound on the maximum number of targets hybridized to a probe. We also present a (1+(d+1)log n)-approximation algorithm to identify at most d targets in the presence of experimental errors. Our approximation algorithms also yield a linear time complexity for the decoding algorithms. The research of T. Znati was supported in part by National Science Foundation under grant CCF-0548895.  相似文献   

11.
The problem of optimal surface flattening in 3-D finds many applications in engineering and manufacturing. However, previous algorithms for this problem are all heuristics without any quality guarantee and the computational complexity of the problem was not well understood. In this paper, we prove that the optimal surface flattening problem is NP-hard. Further, we show that the problem of flattening a topologically spherical surface admits a PTAS and can be solved by a (1+ε)-approximation algorithm in O(nlog n) time for any constant ε>0, where n is the input size of the problem.  相似文献   

12.
In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]2 are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers nk a deterministic o(n 6k−4) time algorithm is given, which finds distributions of n points in [0,1]2 such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)1/(j−2)/n (j−1)/(j−2)).  相似文献   

13.
For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let G (V – s) denote min{c G(X) | Ø X V – s}, where c G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e 1 and e 2 incident to s is called (k, s)-feasible if G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k G (V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n 3 log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n 3 log n) time.  相似文献   

14.
Let G=(V,E) be an undirected graph in which every vertex vV is assigned a nonnegative integer w(v). A w-packing is a collection of cycles (repetition allowed) in G such that every vV is contained at most w(v) times by the members of . Let 〈w〉=2|V|+∑ vV ⌈log (w(v)+1)⌉ denote the binary encoding length (input size) of the vector (w(v): vV) T . We present an efficient algorithm which finds in O(|V|8w2+|V|14) time a w-packing of maximum cardinality in G provided packing and covering cycles in G satisfy the ℤ+-max-flow min-cut property.  相似文献   

15.
Let G=(V,E) be a graph without isolated vertices. A set SV is a paired-dominating set if every vertex in VS is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng (Discrete Appl. Math. 155:2077–2086, 2007), we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs. In addition, we prove that paired-domination problem is NP-complete for bipartite graphs, chordal graphs, even for split graphs.  相似文献   

16.
This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset XV and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log 2 e(G)⌉≤t(G)≤⌈log 2 e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤24 or for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤25 or for k≥6. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013. G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.  相似文献   

17.
In a graph G, a vertex dominates itself and its neighbors. A subset SeqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of GS at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ m , and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r k (G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r k (G m ) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r k (G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r k (G,ddom) < 3n/4 + 2k/7. These bounds are sharp. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.  相似文献   

18.
Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C k (u,v). A k-container is a k *-container if it spans all vertices of G. We define G to be a k *-laceable graph if there is a k *-container joining any two vertices from different partite sets. A k *-container C k *(u,v)={P 1,…,P k } is equitable if ||V(P i )|−|V(P j )||≤2 for all 1≤i,jk. A graph is equitably k *-laceable if there is an equitable k *-container joining any two vertices in different partite sets. Let Q n be the n-dimensional hypercube. In this paper, we prove that the hypercube Q n is equitably k *-laceable for all kn−4 and n≥5. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013.  相似文献   

19.
Given a graph G with nonnegative edge costs and an integer k, we consider the problem of finding an edge subset S of minimum total cost with respect to the constraint that S covers exactly k vertices of G. An O(n 3) algorithm is presented where n is the order of G. It is based on the author's previous paper dealing with a similar problem asking S to cover at least k vertices.  相似文献   

20.
It is well known that if G is a multigraph then χ′(G)≥χ*(G):=max {Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ*(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max {2|E(G[U])|/(|U|−1):UV(G),|U|≥3, |U| is odd}. The conjecture that χ′(G)≤max {Δ(G)+1,⌈Γ(G)⌉} was made independently by Goldberg (Discret. Anal. 23:3–7, 1973), Anderson (Math. Scand. 40:161–175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423–460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ*(G)+c χ*(G) when χ*(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>(11Δ(G)+8)/10; and Scheide recently improved this bound to χ′(G)>(15Δ(G)+12)/14. We prove this conjecture for multigraphs G with $\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor , improving the above mentioned results. As a consequence, for multigraphs G with $\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2} the answer to a 1964 problem of Vizing is in the affirmative.  相似文献   

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

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