Search

Let us be given a rooted digraph D = ( V + s , A ) with a designated root vertex s . Edmonds' seminal result [Edmonds, J., Edge-disjoint branchings , in: B. Rustin (ed.) Combinatorial Algorithms, Academic Press, New York, 91–96 (1973] states that D has a packing of k spanning s -arborescences if and only if D has a packing of k ( s , t )-paths for all t ∈ V , where a packing means arc-disjoint subgraphs. Let M be a matroid on the set of arcs leaving s . A packing of ( s , t )-paths is called M -based if their arcs leaving s form a base of M while a packing of s -arborescences is called M -based if, for all t ∈ V , the packing of ( s , t )-paths provided by the arborescences is M -based. Durand de Gevigney, Nguyen and Szigeti proved in [Durand de Gevigney, O., V.H. Nguyen, and Z. Szigeti, Matroid-based packing of arborescences , SIAM J. Discrete Math., 27 (2013), 567–574] that D has an M -based packing of s -arborescences if and only if D has an M -based packing of ( s , t )-paths for all t ∈ V . Berczi and Frank conjectured that this statement can be strengthened in the sense of Edmonds' theorem such that each s -arborescence is required to be spanning. Specifically, they conjectured that D has an M -based packing of spanning s -arborescences if and only if D has an M -based packing of ( s , t )-paths for all t ∈ V . We disprove this conjecture in its general form and we prove that the corresponding decision problem is NP-complete. However, we prove that the conjecture holds for several fundamental classes of matroids, such as graphic matroids and transversal matroids.

In this paper, we study the location-aware targeted influence maximization problem in social networks, which finds a seed set to maximize the influence spread over the targeted users. In particular, we consider those users who have both topic and geographical preferences on promotion products as targeted users. To efficiently solve this problem, one challenge is how to find the targeted users and compute their preferences efficiently for given requests. To address this challenge, we devise a TR-tree index structure, where each tree node stores users' topic and geographical preferences. By traversing the TR-tree in depth-first order, we can efficiently find the targeted users. Another challenge of the problem is to devise algorithms for efficient seeds selection. We solve this challenge from two complementary directions. In one direction, we adopt the maximum influence arborescence (MIA) model to approximate the influence spread, and propose two efficient approximation algorithms with 1−1/e approximation ratio, which prune some candidate seeds with small influences by precomputing users' initial influences offline and estimating the upper bound of their marginal influences online. In the other direction, we propose a fast heuristic algorithm to improve efficiency. Experiments conducted on real-world data sets demonstrate the effectiveness and efficiency of our proposed algorithms.

Let D be a finite digraph, and let be nonempty subsets of . The (strong form of) Edmonds' branching theorem states that there are pairwise edge-disjoint spanning branchings in D such that the root set of is if and only if for all the number of ingoing edges of X is greater than or equal to the number of sets disjoint from X. As was shown by R. Aharoni and C. Thomassen (J Graph Theory 13 (1989), 71–74), this theorem does not remain true for infinite digraphs. Thomassen also proved that for the class of digraphs without backward-infinite paths, the above theorem of Edmonds remains true. Our main result is that for digraphs without forward-infinite paths, Edmonds' branching theorem remains true as well.

We consider the Erd\H{o}s-R\'enyi random directed graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let $\mathcal{D}(n,m)$ be a graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ($i=1,2,\ldots, m$) of $\mathcal{D}(n,m)$ independently chooses a colour, taken uniformly at random from a given set of $n(1 + O( \log \log n / \log n)) = n (1+o(1))$ colours. We stop the process prematurely at time $M$ when the following two events hold: $\mathcal{D}(n,M)$ has at most one vertex that has in-degree zero and there are at least $n-1$ distinct colours introduced ($M= n(n-1)$ if at the time when all edges are present there are still less than $n-1$ colours introduced; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether $\mathcal{D}(n,M)$ has a rainbow arborescence (that is, a directed, rooted tree on $n$ vertices in which all edges point away from the root and all the edges are different colours). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is "yes".

In this paper, we propose the problem of identifying a minimum-weight rooted not-necessarily-spanning arborescence (MRA) in a directed rooted acyclic graph with weights on arcs. We show this problem to be NP-hard and formulate it as a zero—one integer program. We develop a heuristic H to construct a rooted arborescence (RA) in a given graph G, giving an upper bound. We also formulate a Lagrangian problem, LMRA, by relaxing one set of constraints of the zero—one integer program. For a given set of Lagrange multipliers, LMRA can be easily solved to obtain a lower bound. Then, we propose a Lagrangian heuristic, L, that generates both a lower bound and an upper bound in each iteration. The above heuristics were tested with 50 test problems. We also compared the performance of L with a general-purpose optimization package, CPLEX, using 12 test problems. The results show that L was able to identify an optimal solution in almost all cases. CPLEX found an optimal solution in all cases, but was not able to verify optimality in some instances. © 2002 Wiley Periodicals, Inc.

We address a practical problem which arises in several areas, including network design and VLSI circuit layout. Given an undirected weighted graph G = (V, E) and a family N = {N 1 , ..., N k } of k disjoint groups of nodes N i ⊆ V, the Group Steiner Problem asks for a minimumcost tree which contains at least one node from each group N i- In this paper, we give polynomial-time O(k e )-approximation algorithms for any fixed e > 0. This result improves the previously known O(k)-approximation. We also apply our approximation algorithms to the Steiner problem in directed graphs, while guaranteeing the same performance ratio.

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.g., in the design of distribution networks in which finite resources are available at each node. Some main classes of cuts are described, and the corresponding separation algorithms are presented. Also, we outline a procedure to extend to RMWA some known classes of valid inequalities for the asymmetric traveling salesman problem. New heuristic procedures to compute near-optimal feasible solutions are proposed, which proved to be very effective to reduce the overall computing time spent by the branch-and-cut algorithm. Computational experience on three classes of test problems involving up to 500 vertices is reported, showing that the proposed approach outperforms other published methods.

This paper presents two partition methods that speed up iterative search methods applied to vehicle routing problems including a large number of vehicles. Indeed, using a simple implementation of taboo search as an iterative search method, every best-known solution to classical problems was found. The first partition method (based on a partition into polar regions) is appropriate for Euclidean problems whose cities are regularly distributed around a central depot. The second partition method is suitable for any problem and is based on the arborescence built from the shortest paths from any city to the depot. Finally, solutions that are believed to be optimum are given for problems generated on a grid. © 1993 by John Wiley & Sons, Inc.

We present some existing and some new formulations for the Steiner tree and Steiner arborescence problems. We show the equivalence of many of these formulations. In particular, we establish the equivalence between the classical bidirected dicut relaxation and two vertex weighted undirected relaxations. The motivation behind this study is a characterization of the feasible region of the dicut relaxation in the natural space corresponding to the Steiner tree problem. 0 7993 by John Wiley & Sons, Inc.

To study the long-term characteristics of XLPE cables installed in free air and in water, aging tests were conducted under various testing conditions using XLPE cables with both 3.5 mm and 6 mm insulation. From the Weibull plots of lifetime distribution under the voltage stress EL as the minimum breakdown strength, the minimum value of time to breakdown tL under the constant voltage was estimated. The results of accelerated aging tests of XLPE cables installed in free air demonstrated that the V-t characteristics of XLPE cables could not be described by the conventional inverse power law (t ∝ V−n) with a single constant life exponent n. Based on the microscopic observation of a sliced insulation removed from XLPE cables, it was concluded that bow-tie trees with longer tree length observed in cables tested in water were caused by the moisture from outside, whereas the trees in cables tested in free air were caused by the residual moisture originally existing in the insulation. The breakdown strength of the aged cables tested in water increases through cable drying. However, it does not recover to the original values.

The resource-constrained minimum weighted arborescence problem, a 0-1 integer programming model with application in hierarchical distribution network design, is introduced. Since the model is NP-hard, an enumeration method is required to solve it to optimality. Lagrangean decomposition, a special form of Lagrangean relaxation, is applied to the model. Both analytically and empirically, Lagrangean decomposition is shown to improve on bounds obtained by a conventional Lagrangean relaxation. An enumeration algorithm, that embeds a specialized Lagrangean dual ascent scheme to solve a Lagrangean decomposition dual, is designed, and problems with up to 1000 0-1 variables are solved.

Summary The literature on pachycaul wood anatomy is reviewed. A simple mathematical proof discrediting Carlquist's ‘Theory of paedomorphosis in dicotyledonous woods’ is presented. In contrast to Carlquist's notion of juvenile wood patterns in mature pachycaul plants, it is shown that the narrow-pithed leptocauls have wood patterns much like those of the juvenile stages of pachycauls. Leptocauls do not become pachycaul on islands; arborescent plants in ‘herbaceous’ families on islands are more easily explained as derived from pachycaul microspermous ancestors undergoing tree-building in isolation from competition on the continents.

Vertices are the points in an arborescence which interconnect segments and comprise terminal or pendant vertices (Vp), nodal or branching points and the root point. Branching points may be dichotomous (Vd) or trichomtomous (Vt), etc., and are subdivided into distinct two-dimensional topological entities according to the number of terminal vertices they drain, i.e. Vds comprise primary vertices (Va), connecting two Vps; secondary vertices (Vb), connecting one Vp and one Vd or one Vt; and tertiary vertices (Vc), connecting either two Vds, two Vts or one Vt and one Vd. The four types of Vt (Va', Vb', Vc', Vd') similarly connect three, two, one and zero Vps respectively. Each Vt may be transformed into two Vds thus, Va' = Va + Vb; Vb' = Va/3 + 4Vb/3 + Vc/3; Vc' = Vb + Vc and Vd' = 2Vc. Analysis proceeds by transforming mixed trees containing varying proportions of Vds and Vts into entirely dichotomous branching structures. The topology is then defined by the Va/Vb ratio which has a unique value according to the mode of growth and the frequency of Vts. Vertices are ordered by a centrifugal technique. The frequency distribution of vertices of different order allow the changes in growth characteristics and in remodelling to be detected within particular regions of the tree. Metrical parameters are readily incorporated into the analysis since all vertices are interconnected by segments of finite length and are given the same order magnitude as the vertex they drain. The analytical capabilities of the method are exemplified by its application to the study of growth and plasticity in the dendritic trees of Purkinje cells in the mouse. Growth is defined in metrical and topological terms and sites of reorganization within the mature tree are identified.