共查询到20条相似文献,搜索用时 359 毫秒
1.
Pierangela Veneziani 《Discrete Mathematics》2008,308(24):6009-6014
The bound known as Hunter’s bound states that , where T designates the heaviest spanning tree of the graph on n nodes with edge weights pi,j. We prove that Hunter’s bound is optimal if and only if the input probabilities are given on a tree. 相似文献
2.
In the group Steiner problem we are given an edge-weighted graph G=(V,E,w) and m subsets of vertices . Each subset gi is called a group and the vertices in ?igi are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group.We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant ε>0, our algorithm gives an approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of in the approximation ratio, where |V| is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(maxi|gi|)·logm) provided by the LP based approaches. 相似文献
3.
Roberto Beneduci 《Linear algebra and its applications》2010,433(6):1224-1239
Our starting point is the proof of the following property of a particular class of matrices. Let T={Ti,j} be a n×m non-negative matrix such that ∑jTi,j=1 for each i. Suppose that for every pair of indices (i,j), there exists an index l such that Ti,l≠Tj,l. Then, there exists a real vector k=(k1,k2,…,km)T,ki≠kj,i≠j;0<ki?1, such that, if i≠j.Then, we apply that property of matrices to probability theory. Let us consider an infinite sequence of linear functionals , corresponding to an infinite sequence of probability measures {μ(·)(i)}i∈N, on the Borel σ-algebra such that, . The property of matrices described above allows us to construct a real bounded one-to-one piecewise continuous and continuous from the left function f such that
4.
5.
6.
Gerard J. Chang Jer-Jeong Chen David Kuo Sheng-Chyang Liaw 《Discrete Applied Mathematics》2007,155(8):1007-1013
For positive integers j?k, an L(j,k)-labeling of a digraph D is a function f from V(D) into the set of nonnegative integers such that |f(x)-f(y)|?j if x is adjacent to y in D and |f(x)-f(y)|?k if x is of distance two to y in D. Elements of the image of f are called labels. The L(j,k)-labeling problem is to determine the -number of a digraph D, which is the minimum of the maximum label used in an L(j,k)-labeling of D. This paper studies -numbers of digraphs. In particular, we determine -numbers of digraphs whose longest dipath is of length at most 2, and -numbers of ditrees having dipaths of length 4. We also give bounds for -numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining -numbers of ditrees whose longest dipath is of length 3. 相似文献
7.
8.
Anvesh Komuravelli 《Discrete Applied Mathematics》2009,157(16):3372-3385
An N-dimensional digital binary image (I) is a function I:ZN→{0,1}. I is connected if and only if its black pixels and white pixels are each (3N−1)-connected. I is only connected if and only if its black pixels are (3N−1)-connected. For a 3-D binary image, the respective connectivity models are and . A pair of (3N−1)-neighboring opposite-valued pixels is called interchangeable in a N-D binary image I, if reversing their values preserves the original connectedness. We call such an interchange to be a (3N−1)-local interchange. Under the above connectivity models, we show that given two binary images of n pixels/voxels each, we can transform one to the other using a sequence of (3N−1)-local interchanges. The specific results are as follows. Any two -connected 3-dimensional images I and J each having n black voxels are transformable using a sequence of O((c1+c2)n2) 26-local interchanges. Here, c1 and c2 are the total number of 8-connected components in all 2-dimensional layers of I and J respectively. We also show bounds on connectivity under a different interchange model as proposed in [A. Dumitrescu, J. Pach, Pushing squares around, Graphs and Combinatorics 22 (1) (2006) 37-50]. Next, we show that any two simply connected images under the , connectivity model and each having n black voxels are transformable using a sequence of O(n2) 26-local interchanges. We generalize this result to show that any two , -connected N-dimensional simply connected images each having n black pixels are transformable using a sequence of O(Nn2)(3N−1)-local interchanges, where N>1. 相似文献
9.
10.
11.
12.
13.
B.V. Subramanya Bharadwaj 《Discrete Mathematics》2009,309(4):834-1274
Let G=(V,E) be a finite, simple and undirected graph. For S⊆V, let δ(S,G)={(u,v)∈E:u∈S and v∈V−S} be the edge boundary of S. Given an integer i, 1≤i≤|V|, let the edge isoperimetric value of G at i be defined as be(i,G)=minS⊆V;|S|=i|δ(S,G)|. The edge isoperimetric peak of G is defined as be(G)=max1≤j≤|V|be(j,G). Let bv(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees.The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as ), and where c1, c2 are constants. For a complete t-ary tree of depth d (denoted as ) and d≥clogt where c is a constant, we show that and where c1, c2 are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree — the root being the vertex r. Define a weight function w:V→N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):u∈V}|. For a positive integer k, let ?(k)=|{i∈N:1≤i≤|V|,be(i,G)≤k}|. We show that . 相似文献
14.
Let Δ(T) and μ(T) denote the maximum degree and the Laplacian spectral radius of a tree T, respectively. Let Tn be the set of trees on n vertices, and . In this paper, we determine the two trees which take the first two largest values of μ(T) of the trees T in when . And among the trees in , the tree which alone minimizes the Laplacian spectral radius is characterized. We also prove that for two trees T1 and T2 in , if Δ(T1)>Δ(T2) and , then μ(T1)>μ(T2). As an application of these results, we give a general approach about extending the known ordering of trees in Tn by their Laplacian spectral radii. 相似文献
15.
Francesca Fiorenzi 《Discrete Applied Mathematics》2011,159(17):2045-2049
16.
For a given m×n nonnegative real matrix A, a segmentation with 1-norm relative error e is a set of pairs (α,S)={(α1,S1),(α2,S2),…,(αk,Sk)}, where each αi is a positive number and Si is an m×n binary matrix, and , where |A|1 is the 1-norm of a vector which consists of all the entries of the matrix A. In certain radiation therapy applications, given A and positive scalars γ,δ, we consider the optimization problem of finding a segmentation (α,S) that minimizes subject to certain constraints on Si. This problem poses a major challenge in preparing a clinically acceptable treatment plan for Intensity Modulated Radiation Therapy (IMRT) and is known to be NP-hard. Known discrete IMRT algorithms use alternative objectives for this problem and an L-level entrywise approximation (i.e. each entry in A is approximated by the closest entry in a set of L equally-spaced integers), and produce a segmentation that satisfies . In this paper we present two algorithms that focus on the original non-discretized intensity matrix and consider measures of delivery quality and complexity (∑αi+γk) as well as approximation error e. The first algorithm uses a set partitioning approach to approximate A by a matrix that leads to segmentations with smaller k for a given e. The second algorithm uses a constrained least square approach to post-process a segmentation of to replace with real-valued αi in order to reduce k and e. 相似文献
17.
L Foissy 《Bulletin des Sciences Mathématiques》2003,127(6):505-548
We introduce a functor from the category of braided spaces into the category of braided Hopf algebras which associates to a braided space V a braided Hopf algebra of planar rooted trees . We show that the Nichols algebra of V is a subquotient of . We construct a Hopf pairing between and , generalising one of the results of [Bull. Sci. Math. 126 (2002) 193-239]. When the braiding of c is given by c(vi⊗vj)=qi,jvj⊗vi, we obtain a quantification of the Hopf algebras introduced in [Bull. Sci. Math. 126 (2002) 193-239; 126 (2002) 249-288]. When qi,j=qai,j, with q an indeterminate and (ai,j)i,j the Cartan matrix of a semi-simple Lie algebra , then is a subquotient of . In this case, we construct the crossed product of with a torus and then the Drinfel'd quantum double of this Hopf algebra. We show that is a subquotient of . 相似文献
18.
An independent set of a graph G is a set of pairwise non-adjacent vertices. Let α(G) denote the cardinality of a maximum independent set and fs(G) for 0≤s≤α(G) denote the number of independent sets of s vertices. The independence polynomial defined first by Gutman and Harary has been the focus of considerable research recently. Wingard bounded the coefficients fs(T) for trees T with n vertices: for s≥2. We generalize this result to bounds for a very large class of graphs, maximal k-degenerate graphs, a class which includes all k-trees. Additionally, we characterize all instances where our bounds are achieved, and determine exactly the independence polynomials of several classes of k-tree related graphs. Our main theorems generalize several related results known before. 相似文献
19.
20.