Log in

Relevant bibliographies by topics / Trees (Graph theory) Spanning trees (Graph theory) / Journal articles

To see the other types of publications on this topic, follow the link: Trees (Graph theory) Spanning trees (Graph theory).

Journal articles on the topic 'Trees (Graph theory) Spanning trees (Graph theory)'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Trees (Graph theory) Spanning trees (Graph theory).'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

JOHANNSEN, DANIEL, MICHAEL KRIVELEVICH, and WOJCIECH SAMOTIJ. "Expanders Are Universal for the Class of All Spanning Trees." Combinatorics, Probability and Computing 22, no. 2 (January 3, 2013): 253–81. http://dx.doi.org/10.1017/s0963548312000533.

Full text

Abstract:

A graph is calleduniversalfor a given graph class(or, equivalently,-universal) if it contains a copy of every graph inas a subgraph. The construction of sparse universal graphs for various classeshas received a considerable amount of attention. There is particular interest in tight-universal graphs, that is, graphs whose number of vertices is equal to the largest number of vertices in a graph from. Arguably, the most studied case is that whenis some class of trees. In this work, we are interested in(n,Δ), the class of alln-vertex trees with maximum degree at most Δ. We show that everyn-vertex graph satisfying certain natural expansion properties is(n,Δ)-universal. Our methods also apply to the case when Δ is some function ofn. Since random graphs are known to be good expanders, our result implies, in particular, that there exists a positive constantcsuch that the random graphG(n,cn−1/3log2n) is asymptotically almost surely (a.a.s.) universal for(n,O(1)). Moreover, a corresponding result holds for the random regular graph of degreecn2/3log2n. Another interesting consequence is the existence of locally sparsen-vertex(n,Δ)-universal graphs. For example, we show that one can (randomly) constructn-vertex(n,O(1))-universal graphs with clique number at most five. This complements the construction of Bhatt, Chung, Leighton and Rosenberg (1989), whose(n,Δ)-universal graphs with merelyO(n)edges contain large cliques of size Ω(Δ). Finally, we show that random graphs are robustly(n,Δ)-universal in the context of the Maker–Breaker tree-universality game.

APA, Harvard, Vancouver, ISO, and other styles

2

Janson, Svante. "Random trees in a graph and trees in a random graph." Mathematical Proceedings of the Cambridge Philosophical Society 100, no. 2 (September 1986): 319–30. http://dx.doi.org/10.1017/s0305004100066111.

Full text

Abstract:

This paper treats two related sets of problems in the theory of random graphs. In Sections 2 and 3 we study random spanning subtrees of a complete graph (or, equivalently, random labelled trees). It is shown that the number of common edges of two such random trees asymptotically has a Poisson distribution with expectation 2. Similar results are obtained for the number of edges in the intersection or union of more than two random trees.

APA, Harvard, Vancouver, ISO, and other styles

3

DARMANN, ANDREAS. "POPULAR SPANNING TREES." International Journal of Foundations of Computer Science 24, no. 05 (August 2013): 655–77. http://dx.doi.org/10.1142/s0129054113500226.

Full text

Abstract:

Combinatorial Optimization is combined with Social Choice Theory when the goal is to decide on the quality of a spanning tree of an undirected graph. Given individual preferences over the edges of the graph, spanning trees are compared by means of a Condorcet criterion. The comparisons are based on scoring functions used in classic voting rules such as approval voting and Borda voting. In this work, we investigate the computational complexity involved in deciding on the quality of a spanning tree with respect to the different voting rules adapted. In particular, we draw the sharp separation line between polynomially solvable and computationally intractable instances.

APA, Harvard, Vancouver, ISO, and other styles

4

Li, Feng. "The Number of Spanning Trees in the Composition Graphs." Mathematical Problems in Engineering 2014 (2014): 1–5. http://dx.doi.org/10.1155/2014/613685.

Full text

Abstract:

Using the composition of some existing smaller graphs to construct some large graphs, the number of spanning trees and the Laplacian eigenvalues of such large graphs are also closely related to those of the corresponding smaller ones. By using tools from linear algebra and matrix theory, we establish closed formulae for the number of spanning trees of the composition of two graphs with one of them being an arbitrary complete 3-partite graph and the other being an arbitrary graph. Our results extend some of the previous work, which depend on the structural parameters such as the number of vertices and eigenvalues of the small graphs only.

APA, Harvard, Vancouver, ISO, and other styles

5

Boaventura-Netto, Paulo Oswaldo. "Ranking graph edges by the weight of their spanning arborescences or trees." Pesquisa Operacional 28, no. 1 (April 2008): 59–73. http://dx.doi.org/10.1590/s0101-74382008000100004.

Full text

Abstract:

A result based on a classic theorem of graph theory is generalized for edge-valued graphs, allowing determination of the total value of the spanning arborescences with a given root and containing a given arc in a directed valued graph. A corresponding result for undirected valued graphs is also presented. In both cases, the technique allows for a ranking of the graph edges by importance under this criterion. This ranking is proposed as a tool to determine the relative importance of the edges of a graph in network vulnerability studies. Some examples of application are presented.

APA, Harvard, Vancouver, ISO, and other styles

6

Vasconcellos, Jucele França de Alencar, Edson Norberto Cáceres, Henrique Mongelli, Siang Wun Song, Frank Dehne, and Jayme Luiz Szwarcfiter. "New BSP/CGM algorithms for spanning trees." International Journal of High Performance Computing Applications 33, no. 3 (October 14, 2018): 444–61. http://dx.doi.org/10.1177/1094342018803672.

Full text

Abstract:

Computing a spanning tree (ST) and a minimum ST (MST) of a graph are fundamental problems in graph theory and arise as a subproblem in many applications. In this article, we propose parallel algorithms to these problems. One of the steps of previous parallel MST algorithms relies on the heavy use of parallel list ranking which, though efficient in theory, is very time-consuming in practice. Using a different approach with a graph decomposition, we devised new parallel algorithms that do not make use of the list ranking procedure. We proved that our algorithms are correct, and for a graph [Formula: see text], [Formula: see text], and [Formula: see text], the algorithms can be executed on a Bulk Synchronous Parallel/Coarse Grained Multicomputer (BSP/CGM) model using [Formula: see text] communications rounds with [Formula: see text] computation time for each round. To show that our algorithms have good performance on real parallel machines, we have implemented them on graphics processing unit. The obtained speedups are competitive and showed that the BSP/CGM model is suitable for designing general purpose parallel algorithms.

APA, Harvard, Vancouver, ISO, and other styles

7

LI, WENBO V., and XINYI ZHANG. "On the Difference of Expected Lengths of Minimum Spanning Trees." Combinatorics, Probability and Computing 18, no. 3 (May 2009): 423–34. http://dx.doi.org/10.1017/s0963548308009590.

Full text

Abstract:

An exact formula for the expected length of the minimum spanning tree of a connected graph, with independent and identical edge distribution, is given, which generalizes Steele's formula in the uniform case. For a complete graph, the difference of expected lengths between exponential distribution, with rate one, and uniform distribution on the interval (0, 1) is shown to be positive and of rate ζ(3)/n. For wheel graphs, precise values of expected lengths are given via calculations of the associated Tutte polynomials.

APA, Harvard, Vancouver, ISO, and other styles

8

Shang, Yilun. "On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs." Open Mathematics 14, no. 1 (January 1, 2016): 641–48. http://dx.doi.org/10.1515/math-2016-0055.

Full text

Abstract:

Abstract As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition, we establish upper and lower bounds for the Laplacian Estrada index of Г(G) based on the vertex degrees of G. These bounds are also connected with the number of spanning trees in Г(G).

APA, Harvard, Vancouver, ISO, and other styles

9

KOMLÓS, JÁNOS, GÁBOR N. SÁRKÓZY, and ENDRE SZEMERÉDI. "Spanning Trees in Dense Graphs." Combinatorics, Probability and Computing 10, no. 5 (September 2001): 397–416. http://dx.doi.org/10.1017/s0963548301004849.

Full text

Abstract:

In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n0 such that, if n [ges ] n0, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.

APA, Harvard, Vancouver, ISO, and other styles

10

Gavril, Fǎnicǎ. "Generating the maximum spanning trees of a weighted graph." Journal of Algorithms 8, no. 4 (December 1987): 592–97. http://dx.doi.org/10.1016/0196-6774(87)90053-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Mednykh, A. D., and I. A. Mednykh. "On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs." Algebra Colloquium 27, no. 01 (February 25, 2020): 87–94. http://dx.doi.org/10.1142/s1005386720000085.

Full text

Abstract:

Let [Formula: see text] be the generating function for the number [Formula: see text] of spanning trees in the circulant graph Cn(s1, s2, …, sk). We show that F(x) is a rational function with integer coefficients satisfying the property F(x) = F(1/x). A similar result is also true for the circulant graphs C2n(s1, s2, …, sk, n) of odd valency. We illustrate the obtained results by a series of examples.

APA, Harvard, Vancouver, ISO, and other styles

12

Janson, Svante. "The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph." Combinatorics, Probability and Computing 3, no. 1 (March 1994): 97–126. http://dx.doi.org/10.1017/s0963548300001012.

Full text

Abstract:

The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph Gnm are shown to be asymptotically normal if m is neither too large nor too small. At the lowest limit m ≍ n3/2, these numbers are asymptotically log-normal. For Gnp, the numbers are asymptotically log-normal for a wide range of p, including p constant. The same results are obtained for random directed graphs and bipartite graphs. The results are proved using decomposition and projection methods.

APA, Harvard, Vancouver, ISO, and other styles

13

Yamada, Takeo, Seiji Kataoka, and Kohtaro Watanabe. "Listing all the minimum spanning trees in an undirected graph." International Journal of Computer Mathematics 87, no. 14 (November 2010): 3175–85. http://dx.doi.org/10.1080/00207160903329699.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

WEHRLI, S. "A SPANNING TREE MODEL FOR KHOVANOV HOMOLOGY." Journal of Knot Theory and Its Ramifications 17, no. 12 (December 2008): 1561–74. http://dx.doi.org/10.1142/s0218216508006762.

Full text

Abstract:

We show that the Khovanov complex of a connected link diagram D retracts to a subcomplex whose generators are in 2:1 correspondence with the spanning trees of the "black graph" of D. Using this result, we give a new proof of Lee's theorem on the support of Khovanov homology of alternating knots.

APA, Harvard, Vancouver, ISO, and other styles

15

Tan, Xiang Hua, Jian Guo Zhu, Cheng Wen Cai, Kai Rong Yu, and Hao Yun Qian. "The Critical Group of the Vertex Corona of Cycles and Complete Graphs in Industry." Applied Mechanics and Materials 357-360 (August 2013): 2802–5. http://dx.doi.org/10.4028/www.scientific.net/amm.357-360.2802.

Full text

Abstract:

Self-organized criticality is an important theory widely used in various domain such as a variety of industrial accidents, power system, punctuated equilibrium in biology etc.. The Critical Group of the graph is mainly focused on the Abelian sandpile model of self-organized criticality, whose order is the number of spanning trees in the graph, and which is closely connected with the graph Laplacian matrix. In this paper, the main tools will be the computation for Smith normal form of an integer matrix, which can be achieved by the implementation of a series of row and column operations in the ring Ζ of integers. Hence, the structure of the critical group on the vertex corona is determined and it is shown that the Smith normal form is the direct sum of n (m-1)+1cyclic groups. Furthermore, it follows from Kirchooffs Matrix Tree Theorem that the number of spanning trees of the Graph is n (m+1)n (m-1).

APA, Harvard, Vancouver, ISO, and other styles

16

BIDKHORI, HODA, and SHAUNAK KISHORE. "A Bijective Proof of a Theorem of Knuth." Combinatorics, Probability and Computing 20, no. 1 (July 21, 2010): 11–25. http://dx.doi.org/10.1017/s0963548310000192.

Full text

Abstract:

The line graph G of a directed graph G has a vertex for every edge of G and an edge for every path of length 2 in G. In 1967, Knuth used the Matrix Tree Theorem to prove a formula for the number of spanning trees of G, and he asked for a bijective proof [6]. In this paper, we give a bijective proof of Knuth's formula. As a result of this proof, we find a bijection between binary de Bruijn sequences of degree n and binary sequences of length 2n−1. Finally, we determine the critical groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of Levine [7].

APA, Harvard, Vancouver, ISO, and other styles

17

LYONS, RUSSELL. "Identities and Inequalities for Tree Entropy." Combinatorics, Probability and Computing 19, no. 2 (December 15, 2009): 303–13. http://dx.doi.org/10.1017/s0963548309990605.

Full text

Abstract:

The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some new expressions for tree entropy; one uses Fuglede–Kadison determinants, while another uses effective resistance. We use the latter to prove that tree entropy respects stochastic domination. We also prove that tree entropy is non-negative in the unweighted case, a special case of which establishes Lück's Determinant Conjecture for Cayley-graph Laplacians. We use techniques from the theory of operators affiliated to von Neumann algebras.

APA, Harvard, Vancouver, ISO, and other styles

18

FRIEZE, ALAN, and TONY JOHANSSON. "On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph." Combinatorics, Probability and Computing 27, no. 2 (October 9, 2017): 228–44. http://dx.doi.org/10.1017/s0963548317000426.

Full text

Abstract:

Assume that the edges of the complete graphKnare given independent uniform [0, 1] weights. We consider the expected minimum total weightμkofk⩽ 2 edge-disjoint spanning trees. Whenkis large we show thatμk≈k2. Most of the paper is concerned with the casek= 2. We show thatm2tends to an explicitly defined constant and thatμ2≈ 4.1704288. . . .

APA, Harvard, Vancouver, ISO, and other styles

19

Cohen, Joel E. "Connectivity of finite anisotropic random graphs and directed graphs." Mathematical Proceedings of the Cambridge Philosophical Society 99, no. 2 (March 1986): 315–30. http://dx.doi.org/10.1017/s0305004100064239.

Full text

Abstract:

AbstractFor graphs on a finite set of vertices with arbitrary probabilities of independently occurring edges, the reliability is defined as the probability that the graph is connected, and the redundancy as the expected number of spanning trees of the graph. Analogous measures of connectivity are defined for random finite directed graphs with arbitrary probabilities of independently occurring directed edges. Recursive formulas for computing the reliability are known. Determinantal formulas, based on matrix-tree theorems, for computing the redundancy are given here. Among random graphs with a given sum of edge probabilities, the more evenly the probabilities are distributed over potential edges, the larger the redundancy. This inequality, proved using the theory of majorization, in combination with examples shows unexpectedly that conflicts between reliability and redundancy can arise in the design of communication networks modelled by such random graphs. The significance of these calculations for the command and control of nuclear forces is sketched.

APA, Harvard, Vancouver, ISO, and other styles

20

Didiharyono, Didiharyono, and Siti Soraya. "PENERAPAN ALGORITMA GREEDY DALAM MENENTUKAN MINIMUM SPANNING TREES PADA OPTIMISASI JARINGAN LISTRIK JALA." Jurnal VARIAN 1, no. 2 (April 24, 2018): 1–10. http://dx.doi.org/10.30812/varian.v1i2.66.

Full text

Abstract:

This article discusses the applied of greedy algorithm principle in finding the optimum solution in determine minimum spanning tree on graph. Graph theory is one of the studies in discrete mathematics that are widely applied in various scope. This article is a literature study and applied of nets electricity network optimization using Prims algorithm and Kruskal algorithm. Network Nets System is one type of electrical network system construction. Based on results of the study and discussion can be concluded that the application of greedy algorithm using Prims algorithm and Kruskal algorithm in determine minimum spanning tree on its principle is the same. However, after a comparison between the two algorithms we consider that the ideal algorithm used to optimize the nets electric network is the Kruskal algorithm because in the case of the electric network has few sides and many vertices.

APA, Harvard, Vancouver, ISO, and other styles

21

Feng, Lihua, Kexiang Xu, Kinkar Ch Das, Aleksandar Ilić, and Guihai Yu. "The number of spanning trees of a graph with given matching number." International Journal of Computer Mathematics 93, no. 6 (March 17, 2015): 837–43. http://dx.doi.org/10.1080/00207160.2015.1021341.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Jagers, A. A. "A note on the number of spanning trees in a prism graph." International Journal of Computer Mathematics 24, no. 2 (January 1988): 151–54. http://dx.doi.org/10.1080/00207168808803639.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Yan, Weigen, and Shuli Li. "On the vertex-face graphs of triangulations." Electronic Journal of Linear Algebra 36, no. 36 (September 5, 2020): 616–28. http://dx.doi.org/10.13001/ela.2020.5111.

Full text

Abstract:

Let $G=(V(G),E(G))$ be a triangulation with vertex set $V(G)=\{v_1,v_2, \ldots,v_n\}$ and edge set $E(G)$ embedded on an orientable surface with genus $g$. Define $G^{\nabla}$ to be the graph obtained from $G$ by inserting a new vertex $v_{\phi}$ to each face $\phi$ of $G$ and adding three new edges $(u,v_{\phi}),(v,v_{\phi})$ and $(w,v_{\phi})$, where $u, v$ and $w$ are the three vertices on the boundary of $\phi$. Let $G^{\Box}$ be the graph obtained from $G^{\nabla}$ by deleting all edges in $E(G)$ of $G^{\nabla}$. In this paper, first some spectral properties of $G^{\nabla}$ and $G^{\Box}$ are considered, then it is proved that $t(G^{\nabla})=3^{n+4g-3}5^{n-1}t(G)$ and $t(G^{\Box})=3^{n+4g-3}2^{n-1}t(G)$, where $t(G)$ is the number of spanning trees of $G$. As applications, the number of spanning trees and Kirchhoff indices of some lattices in the context of statistical physics are obtained.

APA, Harvard, Vancouver, ISO, and other styles

24

Jalali, Zeinab S., Alireza Rezvanian, and Mohammad Reza Meybodi. "Social network sampling using spanning trees." International Journal of Modern Physics C 27, no. 05 (May 2016): 1650052. http://dx.doi.org/10.1142/s0129183116500522.

Full text

Abstract:

Due to the large scales and limitations in accessing most online social networks, it is hard or infeasible to directly access them in a reasonable amount of time for studying and analysis. Hence, network sampling has emerged as a suitable technique to study and analyze real networks. The main goal of sampling online social networks is constructing a small scale sampled network which preserves the most important properties of the original network. In this paper, we propose two sampling algorithms for sampling online social networks using spanning trees. The first proposed sampling algorithm finds several spanning trees from randomly chosen starting nodes; then the edges in these spanning trees are ranked according to the number of times that each edge has appeared in the set of found spanning trees in the given network. The sampled network is then constructed as a sub-graph of the original network which contains a fraction of nodes that are incident on highly ranked edges. In order to avoid traversing the entire network, the second sampling algorithm is proposed using partial spanning trees. The second sampling algorithm is similar to the first algorithm except that it uses partial spanning trees. Several experiments are conducted to examine the performance of the proposed sampling algorithms on well-known real networks. The obtained results in comparison with other popular sampling methods demonstrate the efficiency of the proposed sampling algorithms in terms of Kolmogorov–Smirnov distance (KSD), skew divergence distance (SDD) and normalized distance (ND).

APA, Harvard, Vancouver, ISO, and other styles

25

DASBACH, OLIVER T., DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN, and NEAL W. STOLTZFUS. "ALTERNATING SUM FORMULAE FOR THE DETERMINANT AND OTHER LINK INVARIANTS." Journal of Knot Theory and Its Ramifications 19, no. 06 (June 2010): 765–82. http://dx.doi.org/10.1142/s021821651000811x.

Full text

Abstract:

A classical result states that the determinant of an alternating link is equal to the number of spanning trees in a checkerboard graph of an alternating connected projection of the link. We generalize this result to show that the determinant is the alternating sum of the number of quasi-trees of genus j of the dessin of a non-alternating link. Furthermore, we obtain formulas for coefficients of the Jones polynomial by counting quantities on dessins. In particular, we will show that the jth coefficient of the Jones polynomial is given by sub-dessins of genus less or equal to j.

APA, Harvard, Vancouver, ISO, and other styles

26

Ma, Fei, and Bing Yao. "An iteration method for computing the total number of spanning trees and its applications in graph theory." Theoretical Computer Science 708 (January 2018): 46–57. http://dx.doi.org/10.1016/j.tcs.2017.10.030.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Boesch, F. T., A. Satyanarayana, and C. L. Suffel. "Some Alternate Characterizations of Reliability Domination." Probability in the Engineering and Informational Sciences 4, no. 2 (April 1990): 257–76. http://dx.doi.org/10.1017/s0269964800001571.

Full text

Abstract:

An important problem in reliability theory is to determine the reliability of a system from the reliability of its components. If E is a finite set of components, then certain subsets of E are prescribed to be the operating states of the system. A formation is any collection F of minimal operating states whose union is E. Reliability domination is defined as the total number of odd cardinality formations minus the total number of even cardinality formations. The purpose of this paper is to establish some new results concerning reliability domination. In the special case where the system can be identified with a graph or digraph, these new results lead to some new graph-theoretic properties and to simple proofs of certain known theorems. The pertinent graph-theoretic properties include spanning trees, acyclic orientations, Whitney's broken cycles, and Tutte's internal activity associated with the chromatic polynomial.

APA, Harvard, Vancouver, ISO, and other styles

28

Vertigan, D. L., and D. J. A. Welsh. "The Computational Complexity of the Tutte Plane: the Bipartite Case." Combinatorics, Probability and Computing 1, no. 2 (June 1992): 181–87. http://dx.doi.org/10.1017/s0963548300000195.

Full text

Abstract:

Along different curves and at different points of the (x, y)-plane the Tutte polynomial evaluates a wide range of quantities. Some of these, such as the number of spanning trees of a graph and the partition function of the planar Ising model, can be computed in polynomial time, others are # P-hard. Here we give a complete characterisation of which points and curves are easy/hard in the bipartite case.

APA, Harvard, Vancouver, ISO, and other styles

29

d’Amore, Fabrizio, and Paolo G. Franciosa. "A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs." International Journal of Computational Geometry & Applications 28, no. 03 (September 2018): 227–53. http://dx.doi.org/10.1142/s021819591850005x.

Full text

Abstract:

In this paper, we study the problem of designing robust algorithms for computing the minimum spanning tree, the nearest neighbor graph, and the relative neighborhood graph of a set of points in the plane, under the Euclidean metric. We use the term “robust” to denote an algorithm that can properly handle degenerate configurations of the input (such as co-circularities and collinearities) and that is not affected by errors in the flow of control due to round-off approximations. Existing asymptotically optimal algorithms that compute such graphs are either suboptimal in terms of the arithmetic precision required for the implementation, or cannot handle degeneracies, or are based on complex data structures. We present a unified approach to the robust computation of the above graphs. The approach is a variant of the general region approach for the computation of proximity graphs based on Yao graphs, first introduced in Ref. 43 (A. C.-C. Yao, On constructing minimum spanning trees in [Formula: see text]-dimensional spaces and related problems, SIAM J. Comput. 11(4) (1982) 721–736). We show that a sparse supergraph of these geometric graphs can be computed in asymptotically optimal time and space, and requiring only double precision arithmetic, which is proved to be optimal. The arithmetic complexity of the approach is measured by using the notion of degree, introduced in Ref. 31 (G. Liotta, F. P. Preparata and R. Tamassia, Robust proximity queries: An illustration of degree-driven algorithm design, SIAM J. Comput. 28(3) (1998) 864–889) and Ref. 3 (J. D. Boissonnat and F. P. Preparata, Robust plane sweep for intersecting segments, SIAM J. Comput. 29(5) (2000) 1401–1421). As a side effect of our results, we solve a question left open by Katajainen27 (J. Katajainen, The region approach for computing relative neighborhood graphs in the [Formula: see text] metric, Computing 40 (1987) 147–161) about the existence of a subquadratic algorithm, based on the region approach, that computes the relative neighborhood graph of a set of points [Formula: see text] in the plane under the [Formula: see text] metric.

APA, Harvard, Vancouver, ISO, and other styles

30

Geissmann, Barbara, and Lukas Gianinazzi. "Parallel Minimum Cuts in Near-linear Work and Low Depth." ACM Transactions on Parallel Computing 8, no. 2 (June 30, 2021): 1–20. http://dx.doi.org/10.1145/3460890.

Full text

Abstract:

We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum cut in an undirected graph. Previous parallel algorithms with poly-logarithmic depth required at least quadratic work in the number of vertices. In a graph with n vertices and m edges, our randomized algorithm computes the minimum cut with high probability in O ( m log 4 n ) work and O (log 3 n ) depth. This result is obtained by parallelizing a data structure that aggregates weights along paths in a tree, in addition exploiting the connection between minimum cuts and approximate maximum packings of spanning trees. In addition, our algorithm improves upon bounds on the number of cache misses incurred to compute a minimum cut.

APA, Harvard, Vancouver, ISO, and other styles

31

Batenkov, Aleksandr, Kirill Batenkov, and Aleksandr Fokin. "Methods for Formation of Telecommunication Network States Sets for Different Measures of Connectivity." SPIIRAS Proceedings 19, no. 3 (June 1, 2020): 644–73. http://dx.doi.org/10.15622/sp.2020.19.3.7.

Full text

Abstract:

Reliability, survivability, and stability analysis tasks are typical not only for telecommunications, but also for systems whose components are subject to one or more types of failures, such as transport, power, mechanical systems, integrated circuits, and even software. The logical approach involves the decomposition of the system into a number of small functional elements, and within telecommunications networks they are usually separate network devices (switches, routers, terminals, etc.), as well as communication lines between them (copper-core, fiber-optic, coaxial cables, wireless media, and other transmission media). Functional relationships also define logical relationships between the failures of individual elements and the failure of the network as a whole. The assumption is also used that device failures are relatively less likely than communication line failures, which implies using the assumption of absolute stability (reliability, survivability) of these devices. Model of a telecommunication network in the form of the generalized model of Erdos–Renyi is presented. In the context of the stability of the telecommunications network, the analyzed property is understood as the connectivity of the network in one form or another. Based on the concept of stochastic connectivity of a network, as the correspondence of a random graph of the connectivity property between a given set of vertices, three connectivity measures are traditionally distinguished: two-pole, multi-pole, and all-pole. The procedures for forming an arbitrary structure of sets of paths and trees for networks are presented, as well as their generalization of multipolar trees. It is noted that multipolar trees are the most common concept of relatively simple chains and spanning trees. Solving such problems will allow us to proceed to calculating the probability of connectivity of graphs for various connectivity measures.

APA, Harvard, Vancouver, ISO, and other styles

32

Chinta, Gautam, Jay Jorgenson, and Anders Karlsson. "Zeta functions, heat kernels, and spectral asymptotics on degenerating families of discrete tori." Nagoya Mathematical Journal 198 (June 2010): 121–72. http://dx.doi.org/10.1017/s0027763000009958.

Full text

Abstract:

AbstractBy a discrete torus we mean the Cayley graph associated to a finite product of finite cycle groups with the generating set given by choosing a generator for each cyclic factor. In this article we examine the spectral theory of the combinatorial Laplacian for sequences of discrete tori when the orders of the cyclic factors tend to infinity at comparable rates. First, we show that the sequence of heat kernels corresponding to the degenerating family converges, after rescaling, to the heat kernel on an associated real torus. We then establish an asymptotic expansion, in the degeneration parameter, of the determinant of the combinatorial Laplacian. The zeta-regularized determinant of the Laplacian of the limiting real torus appears as the constant term in this expansion. On the other hand, using a classical theorem by Kirchhoff, the determinant of the combinatorial Laplacian of a finite graph divided by the number of vertices equals the number of spanning trees, called thecomplexity, of the graph. As a result, we establish a precise connection between the complexity of the Cayley graphs of finite abelian groups and heights of real tori. It is also known that spectral determinants on discrete tori can be expressed using trigonometric functions and that spectral determinants on real tori can be expressed using modular forms on general linear groups. Another interpretation of our analysis is thus to establish a link between limiting values of certain products of trigonometric functions and modular forms. The heat kernel analysis which we employ uses a careful study ofI-Bessel functions. Our methods extend to prove the asymptotic behavior of other spectral invariants through degeneration, such as special values of spectral zeta functions and Epstein-Hurwitz–type zeta functions.

APA, Harvard, Vancouver, ISO, and other styles

33

Chinta, Gautam, Jay Jorgenson, and Anders Karlsson. "Zeta functions, heat kernels, and spectral asymptotics on degenerating families of discrete tori." Nagoya Mathematical Journal 198 (June 2010): 121–72. http://dx.doi.org/10.1215/00277630-2009-009.

Full text

Abstract:

AbstractBy a discrete torus we mean the Cayley graph associated to a finite product of finite cycle groups with the generating set given by choosing a generator for each cyclic factor. In this article we examine the spectral theory of the combinatorial Laplacian for sequences of discrete tori when the orders of the cyclic factors tend to infinity at comparable rates. First, we show that the sequence of heat kernels corresponding to the degenerating family converges, after rescaling, to the heat kernel on an associated real torus. We then establish an asymptotic expansion, in the degeneration parameter, of the determinant of the combinatorial Laplacian. The zeta-regularized determinant of the Laplacian of the limiting real torus appears as the constant term in this expansion. On the other hand, using a classical theorem by Kirchhoff, the determinant of the combinatorial Laplacian of a finite graph divided by the number of vertices equals the number of spanning trees, called the complexity, of the graph. As a result, we establish a precise connection between the complexity of the Cayley graphs of finite abelian groups and heights of real tori. It is also known that spectral determinants on discrete tori can be expressed using trigonometric functions and that spectral determinants on real tori can be expressed using modular forms on general linear groups. Another interpretation of our analysis is thus to establish a link between limiting values of certain products of trigonometric functions and modular forms. The heat kernel analysis which we employ uses a careful study of I-Bessel functions. Our methods extend to prove the asymptotic behavior of other spectral invariants through degeneration, such as special values of spectral zeta functions and Epstein-Hurwitz–type zeta functions.

APA, Harvard, Vancouver, ISO, and other styles

34

Bonnaire, Tony, Nabila Aghanim, Aurélien Decelle, and Marian Douspis. "T-ReX: a graph-based filament detection method." Astronomy & Astrophysics 637 (May 2020): A18. http://dx.doi.org/10.1051/0004-6361/201936859.

Full text

Abstract:

Numerical simulations and observations show that galaxies are not uniformly distributed in the universe but, rather, they are spread across a filamentary structure. In this large-scale pattern, highly dense regions are linked together by bridges and walls, all of them surrounded by vast, nearly-empty areas. While nodes of the network are widely studied in the literature, simulations indicate that half of the mass budget comes from a more diffuse part of the network, which is made up of filaments. In the context of recent and upcoming large galaxy surveys, it becomes essential that we identify and classify features of the Cosmic Web in an automatic way in order to study their physical properties and the impact of the cosmic environment on galaxies and their evolution. In this work, we propose a new approach for the automatic retrieval of the underlying filamentary structure from a 2D or 3D galaxy distribution using graph theory and the assumption that paths that link galaxies together with the minimum total length highlight the underlying distribution. To obtain a smoothed version of this topological prior, we embedded it in a Gaussian mixtures framework. In addition to a geometrical description of the pattern, a bootstrap-like estimate of these regularised minimum spanning trees allowed us to obtain a map characterising the frequency at which an area of the domain is crossed. Using the distribution of halos derived from numerical simulations, we show that the proposed method is able to recover the filamentary pattern in a 2D or 3D distribution of points with noise and outliers robustness with a few comprehensible parameters.

APA, Harvard, Vancouver, ISO, and other styles

35

Kissinger, Aleks, and Arianne Meijer van de Griend. "CNOT circuit extraction for topologically-constrained quantum memories." Quantum Information and Computation 20, no. 7&8 (June 2020): 581–96. http://dx.doi.org/10.26421/qic20.7-8-4.

Full text

Abstract:

Many physical implementations of quantum computers impose stringent memory constraints in which 2-qubit operations can only be performed between qubits which are nearest neighbours in a lattice or graph structure. Hence, before a computation can be run on such a device, it must be mapped onto the physical architecture. That is, logical qubits must be assigned physical locations in the quantum memory, and the circuit must be replaced by an equivalent one containing only operations between nearest neighbours. In this paper, we give a new technique for quantum circuit mapping (a.k.a. routing), based on Gaussian elimination constrained to certain optimal spanning trees called Steiner trees. We give a reference implementation of the technique for CNOT circuits and show that it significantly out-performs general-purpose routines on CNOT circuits. We then comment on how the technique can be extended straightforwardly to the synthesis of CNOT+Rz circuits and as a modification to a recently-proposed circuit simplification/extraction procedure for generic circuits based on the ZX-calculus.

APA, Harvard, Vancouver, ISO, and other styles

36

Zhao, Zongya, Yaqing Cheng, Zhenxin Li, and Yi Yu. "Altered Small-World Networks in First-Episode Schizophrenia Patients during Cool Executive Function Task." Behavioural Neurology 2018 (September 5, 2018): 1–11. http://dx.doi.org/10.1155/2018/2191208.

Full text

Abstract:

At present, little is known about brain functional connectivity and its small-world topologic properties in first-episode schizophrenia (SZ) patients during cool executive function task. In this paper, the Trail Making Test-B (TMT-B) task was used to evaluate the cool executive function of first-episode SZ patients and electroencephalography (EEG) data were recorded from 14 first-episode SZ patients and 14 healthy controls during this cool executive function task. Brain functional connectivity between all pairs of EEG channels was constructed based on mutual information (MI) analysis. The constructed brain functional networks were filtered by three thresholding schemes: absolute threshold, mean degree, and a novel data-driven scheme based on orthogonal minimal spanning trees (OMST), and graph theory was then used to study the topographical characteristics of the filtered brain graphs. Results indicated that the graph theoretical measures of the theta band showed obvious difference between SZ patients and healthy controls. In the theta band, the characteristic path length was significantly longer and the cluster coefficient was significantly smaller in the SZ patients for a wide range of absolute threshold T. However, the cluster coefficient showed no significant changes, and the characteristic path length was still significantly longer in SZ patients when calculated as a function of mean degree K. Interestingly, we also found that only the characteristic path length was significantly longer in SZ patients compared with healthy controls after using the OMST scheme. Pearson correlation analysis showed that the characteristic path length was positively correlated with executive time of TMT-B for the combined SZ patients and healthy controls (r=0.507, P=0.006), but not for SZ patients alone (r=0.072, P=0.612). The above results suggested a less optimal organization of the brain network and could be useful for understanding the pathophysiologic mechanisms underlying cool executive dysfunction in first-episode SZ patients.

APA, Harvard, Vancouver, ISO, and other styles

37

Zelinka, Bohdan. "Infinite paths in locally finite graphs and in their spanning trees." Mathematica Bohemica 128, no. 1 (2003): 71–76. http://dx.doi.org/10.21136/mb.2003.133936.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Śleszyński, Przemysław, and Paweł Sudra. "Zastosowanie metody minimalnego drzewa rozpinającego (najkrótszego dendrytu) w ocenie efektywności i spójności sieci osadniczej województwa mazowieckiego = Application of the minimum spanning tree method in assessing the effectiveness and cohesion of the settlement network of Mazowieckie voivodeship." Przegląd Geograficzny 91, no. 2 (2019): 61–80. http://dx.doi.org/10.7163/przg.2019.2.4.

Full text

Abstract:

Contemporary settlement systems observed in Poland bear numerous traces of historical transformations of rural settlements which took place in the 19th century, at the time of foreign partitioning of Polish territory, in different ways in particular regions. The result of processes occurring from the second half of the 20th century is the extensive development of urban areas, and – after 1990 – chaotic, spontaneous processes of transformation in suburban zones. Research methods using graph theory have been applied for years in investigating settlement networks on various scales. One of the more useful graphs is the minimum spanning tree (MST), which connects all vertices in such a way that the sum of the distances between them is the shortest. This article presents the application of the minimum spanning tree (or shortest dendrite) method with a view to its suitability for determining the degree of dispersion and spatial cohesion of urbanised structures being assessed. Two indicators have been proposed thanks to alignment of the shortest dendrite length to other variables. The settlement network effectiveness indicator is the ratio of MST length to the population in an area. The settlement network cohesion indicator is in turn the ratio of the MST length to population density. Mazowieckie voivodeship has been chosen as the research area, while address points obtained from the central official database collecting data from municipal records have been chosen as the source dataset. Over 1 million address points were considered, in line with their status as at the end of 2016. Minimum spanning trees were plotted for each of the 314 gminas (local-authority areas) aking up the voivodeship, using ArcGIS software. Subsequently, the proposed indicators were calculated by reference to the MSTs. The results were then mapped. The proposed indicators may be helpful in studies on the origin of settlements, allowing areas with varying degrees of uniformity or isolation of building locations to be indicated. They can be made use of in comparative studies, especially concerning rural settlements, in which single-family housing predominates, and hamlets and uildings standing in isolation are present. The effectiveness indicator can be used in the assessment of infrastructural coverage, i.a. in the ontext of the costs of spatial chaos and demographic capacity.

APA, Harvard, Vancouver, ISO, and other styles

39

RICHARDS, DANA, and JEFFREY S. SALOWE. "MIXED SPANNING TREES IN THEORY AND PRACTICE." International Journal of Computational Geometry & Applications 09, no. 03 (June 1999): 277–92. http://dx.doi.org/10.1142/s0218195999000194.

Full text

Abstract:

A mixed spanning tree is a tree that seeks to combine the properties of a minimim weight spanning tree and shortest path tree. We concentrate on the problem for complete Euclidean graphs. A survey of prior algorithms is given and several new algorithms are proposed. New analyses of some known algorithms are provided. All the algorithms are compared empirically and it is shown that the algorithms with the best known performance bounds, perform the worst in practice. Evidence is given to support the hypothesis that the performance depends on the algorithm's use of long edges.

APA, Harvard, Vancouver, ISO, and other styles

40

McKee, Terry A. "Subgraph trees in graph theory." Discrete Mathematics 270, no. 1-3 (August 2003): 3–12. http://dx.doi.org/10.1016/s0012-365x(03)00161-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Baumgart, Matthias. "Partitioning Bispanning Graphs into Spanning Trees." Mathematics in Computer Science 3, no. 1 (November 27, 2009): 3–15. http://dx.doi.org/10.1007/s11786-009-0011-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Baker, Matthew, and Farbod Shokrieh. "Chip-firing games, potential theory on graphs, and spanning trees." Journal of Combinatorial Theory, Series A 120, no. 1 (January 2013): 164–82. http://dx.doi.org/10.1016/j.jcta.2012.07.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Козневски and E. Kozniewski. "Roof Skeletons and Graph Theory Trees." Geometry & Graphics 4, no. 1 (March 17, 2016): 12–20. http://dx.doi.org/10.12737/18054.

Full text

Abstract:

The problem of constructing roofs of many papers [1; 6; 7; 9; etc.]. In this case, some studies suggested to use a computer and special programs [10; 13; 16; etc.]. The geometry of the efficient design of roofs is actual scientific direction, so in the educational process of architectural and building trades made corresponding innovations [2; 8; 14; 15; 17–20; etc.]. The roofs considered in this article are defined as special geometric polyhedral surfaces, on the basis of two assumptions: (1) all eaves of a roof form a planar (simply-connected or k-connected) polygon called the base, (2) every hipped roof end makes the same slope angle with the (horizontal) plane which contains the base. All the vertices and edges of such a roof, forming the roof skeleton, determine a graph. The orthogonal projection of a roof skeleton onto the base plane leads to a planar graph. On the basis of [11] and [12] and continuing the investigations for regular roofs, we formulate further properties which enable studying the shapes of the roofs spread over simply connected v-gons for an arbitrary integer v (v ≥ 3). We also introduce new operations: splitting and grafting of graphs, and formulate some properties of these operations. By means of such operations, the creation of a graph with cycles using two or more trees is possible. In particular, the operation of the grafting of a roof allows modeling an atrial roof.

APA, Harvard, Vancouver, ISO, and other styles

44

Silver, Daniel S., and Susan G. Williams. "Tangles and links: A view with trees." Journal of Knot Theory and Its Ramifications 27, no. 12 (October 2018): 1850061. http://dx.doi.org/10.1142/s021821651850061x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Duan, Cunxiang, Ligong Wang, and Xiangxiang Liu. "Edge connectivity, packing spanning trees, and eigenvalues of graphs." Linear and Multilinear Algebra 68, no. 6 (October 8, 2018): 1077–95. http://dx.doi.org/10.1080/03081087.2018.1529732.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Daoud, S. N. "Number of Spanning Trees of Different Products of Complete and Complete Bipartite Graphs." Mathematical Problems in Engineering 2014 (2014): 1–23. http://dx.doi.org/10.1155/2014/965105.

Full text

Abstract:

Spanning trees have been found to be structures of paramount importance in both theoretical and practical problems. In this paper we derive new formulas for the complexity, number of spanning trees, of some products of complete and complete bipartite graphs such as Cartesian product, normal product, composition product, tensor product, symmetric product, and strong sum, using linear algebra and matrix theory techniques.

APA, Harvard, Vancouver, ISO, and other styles

47

Ota, Katsuhiro, and Kenta Ozeki. "Spanning trees in 3-connected -minor-free graphs." Journal of Combinatorial Theory, Series B 102, no. 5 (September 2012): 1179–88. http://dx.doi.org/10.1016/j.jctb.2012.07.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Komjáth, Péter. "Martin's axiom and spanning trees of infinite graphs." Journal of Combinatorial Theory, Series B 56, no. 1 (September 1992): 141–44. http://dx.doi.org/10.1016/0095-8956(92)90013-n.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Li, Guojun, and Lingsheng Shi. "Edge-disjoint spanning trees and eigenvalues of graphs." Linear Algebra and its Applications 439, no. 10 (November 2013): 2784–89. http://dx.doi.org/10.1016/j.laa.2013.08.041.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Dudás, T., and R. Rudolf. "Spanning trees and shortest paths in monge graphs." Computing 60, no. 2 (June 1998): 109–19. http://dx.doi.org/10.1007/bf02684360.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!