首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
We study three families of labeled plane trees. In all these trees, the root is labeled 0 and the labels of two adjacent nodes differ by 0,1, or ?1. One part of the paper is devoted to enumerative results. For each family, and for all j?, we obtain closed form expressions for the following three generating functions: the generating function of trees having no label larger than j; the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled j; and finally the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled at least, j. Strangely enough, all these series turn out to be algebraic, but we have no combinatorial intuition for this algebraicity. The other part of the paper is devoted to deriving limit laws from these enumerative results. In each of our families of trees, we endow the trees of size n with the uniform distribution and study the following random variables: Mn, the largest label occurring in a (random) tree; Xn(j), the number of nodes labeled j; and X(j), the number of nodes labeled j or more. We obtain limit laws for scaled versions of these random variables. Finally, we translate the above limit results into statements dealing with the integrated superBrownian excursion. In particular, we describe the law of the supremum of its support (thus recovering some earlier results obtained by Delmas) and the law of its distribution function at a given point. We also conjecture the law of its density (at a given point). © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006  相似文献   

2.
We study a probabilistic optimization model for min spanning tree, where any vertex v i of the input-graph G(V, E) has some presence probability p i in the final instance G′ ⊂ G that will effectively be optimized. Suppose that when this “real” instance G′ becomes known, a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and one can run a quick algorithm (quicker than one that recomputes from scratch), called modification strategy, that modifies the anticipatory tree T in order to fit G′. The goal is to compute an anticipatory spanning tree of G such that, its modification for any G¢ í GG' \subseteq G is optimal for G′. This is what we call probabilistic min spanning tree problem. In this paper we study complexity and approximation of probabilistic min spanning tree in complete graphs under two distinct modification strategies leading to different complexity results for the problem. For the first of the strategies developed, we also study two natural subproblems of probabilistic min spanning tree, namely, the probabilistic metric min spanning tree and the probabilistic min spanning tree 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.  相似文献   

3.
The group of automorphisms of a tree (partially ordered set where the set of predecessors of an element is well ordered) with no infinite levels enjoys the property that every member is a product of two elements of order ≦2. It is shown that this property—called the bireflection property—fails for some trees having infinite levels. In fact, every subtree of a treeT has the the bireflection property if and only if the tree of all zero-one sequences of length ≦ω with finitely many ones is not embeddable inT.  相似文献   

4.
For any tree T (labelled, not rooted) of order n, it will be shown that the average number of nodes in a subtree of T is at least (n + 2)3, with this minimum achieved iff T is a path. For T rooted, the average number of nodes in a subtree containing the root is at least (n + 1)2 and always exceeds the average over all unrooted subtrees. For the maximum mean, examples show that there are arbitrarily large trees in which the average subtree contains essentially all of the nodes. The mean subtree order as a function on trees is also shown to be monotone with respect to inclusion.  相似文献   

5.
For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k-node tree T, then for every k-node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.  相似文献   

6.
It is known that the joint distribution of the number of nodes of each type of an m‐ary search tree is asymptotically multivariate normal when m ≤ 26. When m ≥ 27, we show the following strong asymptotics of the random vector Xn = t(X, … , X), where X denotes the number of nodes containing i ? 1 keys after having introduced n ? 1 keys in the tree: There exist (nonrandom) vectors X, C, and S and random variables ρ and φ such that (Xn ? nX)/n ? ρ(C cos(τ2log n + φ) + S sin(τ2log n + φ)) →n→∞ 0 almost surely and in L2; σ2 and τ2 denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004  相似文献   

7.
SupposeX is a convex configuration with radius of maximum curvaturer and at most one of the edges joining neighboring points has length strictly greater thanr. We use the variational approach to show the Steiner treeS coincides with the minimal spanning tree and consists of all these edges with a longest edge removed. This generalizes Graham's problem for points on a circle, which we had solved. In addition we describe the minimal spanning tree for certain convex configurations.  相似文献   

8.
A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a1,…, ak) is a color distribution for the complete graph Kn, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph Kn with the above distribution if T is a non‐star multicolored spanning tree of Kn, then there exists a multicolored spanning tree T' of Kn such that T and T' are edge‐disjoint. Also it is shown that if Kn, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007  相似文献   

9.
A labelled tree P is an embedded subtree of a labelled tree T if P can be obtained by deleting some nodes from T: if a node v is deleted, all edges adjacent to v are also deleted and replaced by edges going from the parent of v (if it exists) to the children of v. Deciding whether P is an embedded subtree of T is known to be NP-complete. Given two trees (a target T and a pattern P) and a natural number w, we address two problems: 1) counting the number of windows of T having height exactly w and containing the pattern P as an embedded subtree, and 2) counting the number of slices of T having height exactly w and containing the pattern P as an embedded subtree. Our algorithms run in time O(|T|(wh(P)+2)4|P|), where |T| (respectively, |P|) is the size of T (respectively, P), and h(P) is the height of P. Bibliography: 10 titles. Dedicated to Yu. Matiyasevich on the occasion of his 60th birthday. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 3–53.  相似文献   

10.
A set S of trees of order n forces a tree T if every graph having each tree in S as a spanning tree must also have T as a spanning tree. A spanning tree forcing set for order n that forces every tree of order n. A spanning-tree forcing set S is a test set for panarboreal graphs, since a graph of order n is panarboreal if and only if it has all of the trees in S as spanning trees. For each positive integer n ≠ 1, the star belongs to every spanning tree forcing set for order n. The main results of this paper are a proof that the path belongs to every spanning-tree forcing set for each order n ∉ {1, 6, 7, 8} and a computationally tractable characterization of the trees of order n ≥ 15 forced by the path and the star. Corollaries of those results include a construction of many trees that do not belong to any minimal spanning tree forcing set for orders n ≥ 15 and a proof that the following related decision problem is NP-complete: an instance is a pair (G, T) consisting of a graph G of order n and maximum degree n - 1 with a hamiltonian path, and a tree T of order n; the problem is to determine whether T is a spanning tree of G. © 1996 John Wiley & Sons, Inc.  相似文献   

11.
The maximal covering subtree problem has applications in transportation network design and extensive facility location. A subtree of a network is a tree that is not a full spanning tree. Finding an optimal subtree may involve the two objectives, minimizing the total arc cost or distance of the subtree, and maximizing the subtree's coverage of population or demand at nodes. Coverage may be defined as direct or indirect: indirect coverage requires that a node be within a distance threshold s>0 of the subtree, and direct coverage requires that a node be connected to the subtree (s=0). Previous approaches to this problem have sought to identify optimal subtrees of a parent network that is itself a tree (e.g., a minimum spanning tree). In this paper four new bi-objective zero–one programming models are presented. The first two are models for the problem of finding optimal subtrees on a single spanning tree parent under conditions of (1) direct and (2) indirect coverage. These problems have been addressed previously in the literature. In the third and fourth models, the subtree can be selected from among multiple candidate parent spanning trees simultaneously. The latter models address a new generalization of the first problem and offer both increased flexibility and the potential for a more diverse array of solutions. The models have integer-friendly solution properties and are relatively small in terms of the number of decision variables and constraints. Computational experience is reported for a demonstration problem and results are compared to the results of previous models.  相似文献   

12.
The minimal spanning tree problem of a point set in ak-dimensional Euclidean space is considered and a new version of the multifragmentMST-algorithm of Bentley and Friedman is given. The minimal spanning tree is found by repeatedly joining the minimal subtree with the closest subtree. Ak-d tree is used for choosing the connecting edges. Computation time of the algorithm depends on the configuration of the point set: for normally distributed random points the algorithm is very fast. Two extreme cases demandingO(n logn) andO(n 2) operations,n being the cardinality of the point set, are also given.  相似文献   

13.
In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n < m), and ? = m ? n empty places. For a noncomputer science‐minded reader, we shall use the metaphore of n cars parking on m places: each car ci chooses a place pi at random, and if pi is occupied, ci tries successively pi + 1, pi + 2, until it finds an empty place. Pittel [42] proves that when ?/m goes to some positive limit β < 1, the size B of the largest block of consecutive cars satisfies 2(β ? 1 ? log β)B = 2 log m ? 3 log log m + Ξm, where Ξm converges weakly to an extreme‐value distribution. In this paper we examine at which level for n a phase transition occurs between B = o(m) and m ? B = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 76–119, 2002  相似文献   

14.
Bi-Objective Median Subtree Location Problems   总被引:1,自引:0,他引:1  
A number of network design problems can be built on the following premise: given an undirected tree network, T, with node set, V, identify a single subtree, t, containing nodes, v, so that the subtree is located optimally with respect to the remaining, subset of unconnected nodes {Vv}. Distances between unconnected nodes and nodes in the subtree t can be defined on paths that are restricted to lie in the larger tree T (the restricted case), or can be defined on paths in an auxiliary complete graph G (the unrestricted case). The unrestricted case represents a class of problems that is not explicitly recognized in the literature, which is of intermediate complexity relative to the widely studied restricted case, and the general problem in which the underlying graph is general. This paper presents the Median Subtree Location Problem (MSLP), formulated as a bicriterion problem that trades off the cost of a subtree, t, against the population-weighted travel distance from the unconnected nodes to nodes on the subtree where both objectives are to be minimized. Integer programs were formulated for the travel restricted and travel unrestricted cases and were tested using linear programming and branch and bound to resolve fractions. Tradeoff curves between cost and travel burden were developed for sample networks.  相似文献   

15.
Let H be a random graph on n vertices, grown by adding vertices one at a time, joining each new vertex to a uniformly chosen set of m earlier vertices. If edges of H are deleted independently, each being retained with probability p, then there is a “phase transition”. There is a certain critical value pc of p such that, with high probability, a component of order Θ(n) remains as n → ∞ if and only if p > pc. Among other results, we obtain the exact value of pc, which depends on m in a nontrivial way, and show that the phase transition has “infinite order”; in fact, for p = pc + ?, the largest component has order exp(?Θ(1/ ))n with high probability. Analogous results were proved recently in by Bollobás, Janson, and Riordan [Random Structures Algorithms 26 (2005), 1–36] for a related model in which edges are present independently. The model we study is considerably more difficult to analyze, since the dependence between the edges is very important, affecting the value of pc, so many new complications arise. In overcoming these complications we make use of the techniques developed by the authors [Internet Math 1 (2003), 1–35] to analyze a very different model. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005  相似文献   

16.
This paper is devoted to the study of the Cauchy problem of incompressible magneto‐hydrodynamics system in the framework of Besov spaces. In the case of spatial dimension n?3, we establish the global well‐posedness of the Cauchy problem of an incompressible magneto‐hydrodynamics system for small data and the local one for large data in the Besov space ? (?n), 1?p<∞ and 1?r?∞. Meanwhile, we also prove the weak–strong uniqueness of solutions with data in ? (?n)∩L2(?n) for n/2p+2/r>1. In the case of n=2, we establish the global well‐posedness of solutions for large initial data in homogeneous Besov space ? (?2) for 2<p<∞ and 1?r<∞. Copyright © 2008 John Wiley & Sons, Ltd.  相似文献   

17.
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low-weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning treeTusingadoptionsto meet the degree constraints is considered. A novel network-flow-based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previous algorithm. If the degree constraintd(v) for eachvis at least 2, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times 2 − min{(d(v) − 2)/(degT(v) − 2) : degT(v) > 2}, where degT(v) is the initial degree ofv. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds foranyalgorithm at all, then it also holds for the given algorithm. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. ChoosingTto be a minimum spanning tree yields approximation algorithms with factors less than 2 for the general problem on geometric graphs with distances induced by variousLpnorms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesman path and a minimum spanning tree can be arbitrarily close to 2.  相似文献   

18.
We analyze a fringe tree parameter w in a variety of settings, utilizing a variety of methods from the analysis of algorithms and data structures. Given a tree t and one of its leaves a, the w(t, a) parameter denotes the number of internal nodes in the subtree rooted at a's father. The closely related w?(t, a) parameter denotes the number of leaves, excluding a, in the subtree rooted at a's father. We define the cumulative w parameter as W(t) = Σaw(t, a), i.e. as the sum of w(t, a) over all leaves a of t. The w parameter not only plays an important rôle in the analysis of the Lempel–Ziv '77 data compression algorithm, but it is captivating from a combinatorial viewpoint too. In this report, we determine the asymptotic behavior of the w and W parameters on a variety of types of trees. In particular, we analyze simply generated trees, recursive trees, binary search trees, digital search trees, tries and Patricia tries. The final section of this report briefly summarizes and improves the previously known results about the w? parameter's behavior on tries and suffix trees, originally published in one author's thesis (see Analysis of the multiplicity matching parameter in suffix trees. Ph.D. Thesis, Purdue University, West Lafayette, IN, U.S.A., May 2005; Discrete Math. Theoret. Comput. Sci. 2005; AD :307–322; IEEE Trans. Inform. Theory 2007; 53 :1799–1813). This survey of new results about the w parameter is very instructive since a variety of different combinatorial methods are used in tandem to carry out the analysis. Copyright © 2008 John Wiley & Sons, Ltd.  相似文献   

19.
20.
The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree in a network where nodes have specified demands, with an additional capacity constraints on the subtrees incident to a given source node s. The capacitated minimum spanning tree problem arises as an important subproblem in many telecommunication network design problems. In a recent paper, Ahuja et al. (Math. Program. 91 (2001) 71) proposed two very large-scale neighborhood search algorithms for the capacitated minimum spanning tree problem. Their first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. Their second tree-based neighborhood structure is obtained by performing multi-exchanges where each tree contributes a subtree. The computational investigations found that node-based multi-exchange neighborhood gives the best performance for the homogenous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance for the heterogeneous demand case (when nodes may have different demands). In this paper, we propose a composite neighborhood structure that subsumes both the node-based and tree-based neighborhoods, and outperforms both the previous neighborhood search algorithms for solving the capacitated minimum spanning tree problem on standard benchmark instances. We also develop improved dynamic programming based exact algorithms for searching the composite neighborhood.  相似文献   

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

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