Results 11 to 20 of about 309,634 (292)
Breaking intractability of spanning caterpillar tree problem: A logical approach [PDF]
AUT Journal of Mathematics and Computing, 2022 In this paper we pursue a logical approach to prove that the optimisation problem of finding a spanning caterpillar tree in a graph has polynomial algorithm for bounded tree width graphs.
Masoud Khosravani
doaj +1 more source
Successive minimum spanning trees [PDF]
Random Structures & Algorithms, 2021 AbstractIn a complete graphwith independent uniform(or exponential) edge weights, letbe the minimum‐weight spanning tree (MST), andthe MST after deleting the edges of all previous trees. We show that each tree's weightconverges in probability to a constant, with, and we conjecture that.
Janson, Svante, Sorkin, Gregory B.
openaire +6 more sources
End‐faithful spanning trees in graphs without normal spanning trees [PDF]
Journal of Graph Theory, 2022 AbstractSchmidt characterised the class of rayless graphs by an ordinal rank function, which makes it possible to prove statements about rayless graphs by transfinite induction. Halin asked whether Schmidt's rank function can be generalised to characterise other important classes of graphs. In this paper, we address Halin's question: we characterise an
Carl Bürger, Jan Kurkofka
openaire +3 more sources
Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs
Discussiones Mathematicae Graph Theory, 2022 For an integer k ≥ 2, a k-tree T is defined as a tree with maximum degree at most k. If a k-tree T spans a graph G, then T is called a spanning k-tree of G.
Furuya Michitaka +5 more
doaj +1 more source
Streaming Complexity of Spanning Tree Computation [PDF]
, 2020 The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an n-node input graph to be read sequentially in p passes using Õ(n) space.
+3 more
core +2 more sources
Degree-Constrained k-Minimum Spanning Tree Problem
Complexity, 2020 Let GV,E be a simple undirected complete graph with vertex and edge sets V and E, respectively. In this paper, we consider the degree-constrained k-minimum spanning tree (DCkMST) problem which consists of finding a minimum cost subtree of G formed with ...
Pablo Adasme, Ali Dehghan Firoozabadi
doaj +1 more source
Isolation Forest Based on Minimal Spanning Tree
IEEE Access, 2022 Detecting anomalies in data sets has been one of the most studied issues in modern data analysis. Therefore, there is a plethora of applications in a very wide range of fields of science and technology.
Lukasz Galka +2 more
doaj +1 more source
On the probabilistic min spanning tree Problem [PDF]
, 2010 We study a probabilistic optimization model for min spanning tree, where any vertex vi of the input-graph G(V,E) has some presence probability pi in the final instance G′ ⊂ G that will effectively be optimized.
A Prekopa +27 more
core +6 more sources
The Spanning Tree of a Divisible Multiple Graph
Моделирование и анализ информационных систем, 2018 In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges.
Alexander V. Smirnov
doaj +1 more source
Spanning Trees and bootstrap reliability estimation in correlation based networks [PDF]
, 2006 We introduce a new technique to associate a spanning tree to the average linkage cluster analysis. We term this tree as the Average Linkage Minimum Spanning Tree.
Anderberg M. R. +10 more
core +2 more sources