Search results for "Spanning tree"
showing 10 items of 53 documents
Bootstrap validation of links of a minimum spanning tree
2018
We describe two different bootstrap methods applied to the detection of a minimum spanning tree obtained from a set of multivariate variables. We show that two different bootstrap procedures provide partly distinct information that can be highly informative about the investigated complex system. Our case study, based on the investigation of daily returns of a portfolio of stocks traded in the US equity markets, shows the degree of robustness and completeness of the information extracted with popular information filtering methods such as the minimum spanning tree and the planar maximally filtered graph. The first method performs a "row bootstrap" whereas the second method performs a "pair bo…
Completely independent spanning trees in some regular graphs
2014
International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-1 and a cycle, and some Cartesian products of three cycles (for k = 3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k. (C) 2016 Elsevier B.V. All righ…
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
2017
International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…
A genetic algorithm for image segmentation
2002
The paper describes a new algorithm for image segmentation. It is based on a genetic approach that allow us to consider the segmentation problem as a global optimization problem (GOP). For this purpose, a fitness function, based on the similarity between images, has been defined. The similarity is a function of both the intensity and the spatial position of pixels. Preliminary results, obtained using real images, show a good performance of the segmentation algorithm.
Causality and Loop-Tree Duality at Higher Loops
2019
We relate a $l$-loop Feynman integral to a sum of phase space integrals, where the integrands are determined by the spanning trees of the original $l$-loop graph. Causality requires that the propagators of the trees have a modified $i\delta$-prescription and we present a simple formula for the correct $i\delta$-prescription.
A new minimum spanning tree-based method for shape description and matching working in Discrete Cosine space
2009
In this article, a new minimum spanning tree-based method for shape description and matching is proposed. Its properties are checked through the problem of graphical symbols recognition. Recognition invariance in front shift and multi-oriented noisy objects was studied in the context of small and low resolution binary images. The approach seems to have many desirable properties, even if the construction of graphs induces an expensive algorithmic cost. In order to reduce time computing, an alternative solution based on image compression concepts is provided. The recognition is realized in a compact space, namely the Discrete Cosine space. The use of block discrete cosine transform is discuss…
Edge Orientation and the Design of Problem-Specific Crossover Operators for the OCST Problem
2012
In the Euclidean optimal communication spanning tree problem, the edges in optimal trees not only have small weights but also point with high probability toward the center of the graph. These characteristics of optimal solutions can be used for the design of problem-specific evolutionary algorithms (EAs). Recombination operators of direct encodings like edge-set and NetDir can be extended such that they prefer not only edges with small distance weights but also edges that point toward the center of the graph. Experimental results show higher performance and robustness in comparison to EAs using existing crossover strategies.
On the Bias and Performance of the Edge-Set Encoding
2009
The edge-set encoding of trees directly represents trees as sets of their edges. Nonheuristic operators for edge-sets manipulate trees' edges without regard for their weights, while heuristic operators consider edges' weights when including or excluding them. In the latter case, the operators generally favor edges with lower weights, and they tend to generate trees that resemble minimum spanning trees. This bias is strong, which suggests that evolutionary algorithms (EAs) that employ heuristic operators will succeed when optimum solutions resemble minimum spanning trees (MSTs) but fail otherwise. The one-max tree problem is a scalable test problem for trees where the optimum solution can be…
On Optimal Solutions for the Optimal Communication Spanning Tree Problem
2009
This paper presents an experimental investigation into the properties of the optimal communication spanning tree (OCST) problem. The OCST problem seeks a spanning tree that connects all the nodes and satisfies their communication requirements at a minimum total cost. The paper compares the properties of random trees to the properties of the best solutions for the OCST problem that are found using an evolutionary algorithm. The results show, on average, that the optimal solution and the minimum spanning tree (MST) share a higher number of links than the optimal solution and a random tree. Furthermore, optimal solutions for OCST problems with randomly chosen distance weights share a higher n…
Using penalties instead of rewards: Solving OCST problems with guided local search
2012
Abstract This paper considers the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions and found that edges in optimal solutions have low weight and point towards the center of a tree. Consequently, integrating this problem-specific knowledge into a metaheuristic increases its performance for the OCST problem. In this paper, we present a guided local search (GLS) approach which dynamically changes the objective function to guide the search process into promising areas. In contrast to traditional approaches which reward promising solution features by favoring edges with low weights pointing towards the tree’s center, GLS penalizes low-…