Algorithm 42. Enclosure of a point to the minimum spanning tree

G. Trybuś

The search session has expired. Please query the service again.

Displaying similar documents to “Algorithm 42. Enclosure of a point to the minimum spanning tree”

Descendants and ascendants in binary trees.

Panholzer, Alois, Prodinger, Helmut (1997)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

The color-balanced spanning tree problem

Štefan Berežný, Vladimír Lacko (2005)

Kybernetika

Similarity:

Suppose a graph $G = (V, E)$ whose edges are partitioned into $p$ disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number $p$ of categories and present some polynomial algorithm.

Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems.

Bar-Yehuda, Reuven, Even, Guy, Feldmann, Jon, Naor, Joseph (2001)

Journal of Graph Algorithms and Applications

Similarity:

Spanning trees with leaves bounded by independence number.

Sun, Ling-li (2007)

Applied Mathematics E-Notes [electronic only]

Similarity:

Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem

Bryant Julstrom (2004)

International Journal of Applied Mathematics and Computer Science

Similarity:

The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem...

Variations for spanning trees.

Zsakó, László (2006)

Annales Mathematicae et Informaticae

Similarity:

An efficient connected dominating set algorithm in wsns based on the induced tree of the crossed cube

Jing Zhang, Li Xu, Shu-ming Zhou, Wei Wu, Xiucai Ye (2015)

International Journal of Applied Mathematics and Computer Science

Similarity:

The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms. In this paper, a novel algorithm based on the induced...

Independence number and degree bounded spanning tree.

Rahman, Mohammad Sohel, Kaykobad, Mohammad (2004)

Applied Mathematics E-Notes [electronic only]

Similarity:

Completely Independent Spanning Trees in (Partial) k-Trees

Masayoshi Matsushita, Yota Otachi, Toru Araki (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that [k/2] ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {[k/2], . . . , k − 1}, there exist infinitely many k-trees G such...

Developing new locality results for the Prüfer code using a remarkable linear-time decoding algorithm.

Paulden, Tim, Smith, David K. (2007)

The Electronic Journal of Combinatorics [electronic only]

Similarity: