Relevant bibliographies by topics / Weakly proper spanning tree

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Weakly proper spanning tree'

Author: Grafiati
Published: 25 May 2024

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Weakly proper spanning tree.'

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.

Journal articles on the topic "Weakly proper spanning tree"

1

ALZOUBI, KHALED M., PENG-JUN WAN, and OPHIR FRIEDER. "MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS." International Journal of Foundations of Computer Science 14, no. 02 (2003): 287–303. http://dx.doi.org/10.1142/s012905410300173x.

Full text
Abstract:
A maximal independent set (MIS) S for a graph G is an independent set and no proper superset of S is also independent. A set S is dominating if each node in the graph is either in S or adjacent to one of the nodes in S. The subgraph weakly induced by S is the graph G′ such that each edge in G′ has at least one end point in S. A set S is a weakly-connected dominating set (WCDS) of G if S is dominating and G′ is connected. G′ is a sparse spanner if it has linear edges. The nodes of WCDS have been proposed in the literature as clusterheads for clustered wireless ad hoc networks. In this paper, we present two distributed algorithms for constructing a WCDS for wireless ad hoc networks in linear time. The first algorithm has an approximation ratio of 5, and requires O(n log n) messages, while the second algorithm has a larger approximation ratio, and requires only O(n) messages. Both of these algorithms are used to obtain sparse spanners. The spanner obtained by the second algorithm has a topological dilation of 3, and a geometric dilation of 6. Both of these algorithms are based on the construction of a MIS. The first algorithm requires the construction of a spanning tree. The second algorithm is fully localized, and does not depend on the spanning tree, which makes the maintenance of the WCDS simpler, and guarantees the maintenance of the same approximation ratio.
APA, Harvard, Vancouver, ISO, and other styles
2

Bhatt, Abhay G., and Rahul Roy. "On a random directed spanning tree." Advances in Applied Probability 36, no. 1 (2004): 19–42. http://dx.doi.org/10.1239/aap/1077134462.

Full text
Abstract:
We study the asymptotic properties of a minimal spanning tree formed by n points uniformly distributed in the unit square, where the minimality is amongst all rooted spanning trees with a direction of growth. We show that the number of branches from the root of this tree, the total length of these branches, and the length of the longest branch each converges weakly. This model is related to the study of record values in the theory of extreme-value statistics and this relation is used to obtain our results. The results also hold when the tree is formed from a Poisson point process of intensity n in the unit square.
APA, Harvard, Vancouver, ISO, and other styles
3

Bhatt, Abhay G., and Rahul Roy. "On a random directed spanning tree." Advances in Applied Probability 36, no. 01 (2004): 19–42. http://dx.doi.org/10.1017/s0001867800012854.

Full text
Abstract:
We study the asymptotic properties of a minimal spanning tree formed by n points uniformly distributed in the unit square, where the minimality is amongst all rooted spanning trees with a direction of growth. We show that the number of branches from the root of this tree, the total length of these branches, and the length of the longest branch each converges weakly. This model is related to the study of record values in the theory of extreme-value statistics and this relation is used to obtain our results. The results also hold when the tree is formed from a Poisson point process of intensity n in the unit square.
APA, Harvard, Vancouver, ISO, and other styles
4

Mayliana, Mayliana. "Optimasi Jaringan dengan Spanning Tree untuk Congestion Management." ComTech: Computer, Mathematics and Engineering Applications 5, no. 1 (2014): 53. http://dx.doi.org/10.21512/comtech.v5i1.2582.

Full text
Abstract:
A proper network optimization is needed to deal with problems on the network and to minimize latency in the data flow in a dense network. The data stream is directed into the right channels so that the optimal network speed and latency can be minimized. Spanning tree is one of the algorithms that can be used. The purpose of the Spanning tree is to prevent and reduce the loops in the network by negotiating free path and as well as to increase network uptime through redundancy (back-up). To comprehend spanning tree, the first important thing to know is how bridges and switches perform their functions. The more switches used, the use of the spanning tree becomes more important. With the spanning tree protocol, a broadcast storm can be prevented that can achieved network optimization.
APA, Harvard, Vancouver, ISO, and other styles
5

Penrose, Mathew D. "Extremes for the minimal spanning tree on normally distributed points." Advances in Applied Probability 30, no. 3 (1998): 628–39. http://dx.doi.org/10.1239/aap/1035228120.

Full text
Abstract:
Let n points be placed independently in ν-dimensional space according to the standard ν-dimensional normal distribution. Let Mn be the longest edge-length of the minimal spanning tree on these points; equivalently let Mn be the infimum of those r such that the union of balls of radius r/2 centred at the points is connected. We show that the distribution of (2 log n)1/2Mn - bn converges weakly to the Gumbel (double exponential) distribution, where bn are explicit constants with bn ~ (ν - 1)log log n. We also show the same result holds if Mn is the longest edge-length for the nearest neighbour graph on the points.
APA, Harvard, Vancouver, ISO, and other styles
6

Penrose, Mathew D. "Extremes for the minimal spanning tree on normally distributed points." Advances in Applied Probability 30, no. 03 (1998): 628–39. http://dx.doi.org/10.1017/s000186780000851x.

Full text
Abstract:
Let n points be placed independently in ν-dimensional space according to the standard ν-dimensional normal distribution. Let M n be the longest edge-length of the minimal spanning tree on these points; equivalently let M n be the infimum of those r such that the union of balls of radius r/2 centred at the points is connected. We show that the distribution of (2 log n)1/2 M n - b n converges weakly to the Gumbel (double exponential) distribution, where b n are explicit constants with b n ~ (ν - 1)log log n. We also show the same result holds if M n is the longest edge-length for the nearest neighbour graph on the points.
APA, Harvard, Vancouver, ISO, and other styles
7

Dereniowski, Dariusz. "Minimum vertex ranking spanning tree problem for chordal and proper interval graphs." Discussiones Mathematicae Graph Theory 29, no. 2 (2009): 253. http://dx.doi.org/10.7151/dmgt.1445.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Honma, Hirotoshi, Yoko Nakajima, Shino Nagasaki, and Atsushi Sasaki. "An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs." Journal of Applied Mathematics and Physics 06, no. 08 (2018): 1649–58. http://dx.doi.org/10.4236/jamp.2018.68141.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

FERRAGINA, PAOLO, and FABRIZIO LUCCIO. "THREE TECHNIQUES FOR PARALLEL MAINTENANCE OF A MINIMUM SPANNING TREE UNDER BATCH OF UPDATES." Parallel Processing Letters 06, no. 02 (1996): 213–22. http://dx.doi.org/10.1142/s0129626496000212.

Full text
Abstract:
In this paper we provide three simple techniques to maintain in parallel the minimum spanning tree of an undirected graph under single or batch of edge updates (i.e., insertions and deletions). Our results extend the use of the sparsification data structure to the EREW PRAM model. For proper values of the batch size, our algorithms require less time and work than the best known dynamic parallel algorithms.
APA, Harvard, Vancouver, ISO, and other styles
10

Sisto, Alessandro. "Contracting elements and random walks." Journal für die reine und angewandte Mathematik (Crelles Journal) 2018, no. 742 (2018): 79–114. http://dx.doi.org/10.1515/crelle-2015-0093.

Full text
Abstract:
Abstract We define a new notion of contracting element of a group and we show that contracting elements coincide with hyperbolic elements in relatively hyperbolic groups, pseudo-Anosovs in mapping class groups, rank one isometries in groups acting properly on proper {\mathrm{CAT}(0)} spaces, elements acting hyperbolically on the Bass–Serre tree in graph manifold groups. We also define a related notion of weakly contracting element, and show that those coincide with hyperbolic elements in groups acting acylindrically on hyperbolic spaces and with iwips in {\mathrm{Out}(F_{n})} , {n\geq 3} . We show that each weakly contracting element is contained in a hyperbolically embedded elementary subgroup, which allows us to answer a problem in [16]. We prove that any simple random walk in a non-elementary finitely generated subgroup containing a (weakly) contracting element ends up in a non-(weakly-)contracting element with exponentially decaying probability.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Weakly proper spanning tree"

1

Mendy, Gervais. "Chaînes alternées dans les graphes arête-coloriés : k-linkage et arbres couvrants." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00769929.

Full text
Abstract:
Un graphe arête-colorié Gc est un graphe dont les arêtes sont coloriées par un ensemble de couleurs données. Un sous-graphe de Gc est dit proprement colorié s'il ne contient pas d'arêtes adjacentes de même couleur. Un graphe ou multigraphe c-arête-colorié Gc, est dit k-lié (respectivement k-arête-lié) si et seulement si quelque soient 2k sommets distincts de V(Gc), notés, x1 y1 , x2 y2 , ..., xk yk , il existe k chaînes élémentaires sommet-disjointes (respectivement arête-disjointes) proprement arête-coloriées, reliant x1 à y1 , x2 à y2 , ... , xk à yk .Un arbre couvrant propre d'un graphe Gc est un sous-graphe de Gc qui est un arbre couvrant proprement colorié.Un arbre couvrant faiblement colorié est une arborescence telle qu'il existe une chaîne proprement coloriée entre la racine et chaque sommet du graphe.Dans la première partie de cette thèse, nous donnons des conditions suffisantes pour qu'un graphe arête-colorié soit k-lié. C'est un problème classique en théorie des graphes, avec des applications multiples. Ainsi, nous avons établi entre autres les résultats suivants.A) Tout multigraphe 2-arête-colorié d'ordre n ≥ 242k tel que dc(Gc) ≥ n/2+k -1, est k-lié. B) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k et de taille m≥ cn(n-1)/2 - c(n-2k +1)+1 est k-lié.C) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k tel que dc(x) ≥ n/2 pour tout sommet x, est k-arête-lié.D) Tout multigraphe 2-arête-colorié d'ordre n ≥ 2k ≥ 10 et de taille m ≥ n2 -5n + 11 tel que dc(x) ≥ 1 pour tout sommet x, est k-arête-lié.Dans la seconde partie de cette thèse, deux autres problèmes classiques en théorie des graphes sont traités dans la version arête-coloriée. Il s'agit des arbres couvrants et des chaînes hamiltoniennes. Nous donnons ci-dessous quelques résultats.E) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n-k-1 + k +1, a un arbre couvrant propre.F) Tout graphe Gc connexe c-arête-colorié de degré rainbow rd(Gc)=k et d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n-k-1 + k +1, possède un arbre couvrant propre.G) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ ((k + j)2 + 3(k + j) - 2)/2 avec c ≥ ((n - k - j)(n - k - j - 1))/2 + 2 , où j(j -1)=k , possède un arbre couvrant faiblement colorié.H) Tout multigraphe Gc d'ordre n ≥ 14 et de taille m ≥ (n - 3)(n - 4) + 3n - 2 tel que rd(Gc) = 2, possède une chaîne hamiltonienne propre. I) Tout multigraphe c-arête-colorié d'ordre n ≠ 5, 7 et de taille m ≥ n2 - 3n + 4, possède une chaîne hamiltonienne propre.La plupart des résultats exposés, sont les meilleurs possibles relativement aux propriétés sur les conditions suffisantes.
APA, Harvard, Vancouver, ISO, and other styles
2

Ouyang, Qiancheng. "Some colouring problems in edge/vertex-coloured graphs : Structural and extremal studies." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG060.

Full text
Abstract:
La coloration de graphes est l'un des sujets les plus connus, populaires et largement étudiés dans le domaine de la théorie des graphes, avec une vaste littérature comprenant des approches provenant de nombreux domaines ainsi que de nombreux problèmes qui sont encore ouverts et étudiés par divers mathématiciens et informaticiens à travers le monde. Le Problème des Quatre Couleurs, à l'origine de l'étude de la coloration des graphes, a été l'un des problèmes centraux en théorie des graphes au siècle dernier. Il demande s'il est possible de colorer proprement chaque graphe planaire avec quatre couleurs. Malgré son origine théorique, la coloration des graphes a trouvé de nombreuses applications pratiques telles que la planification, les problèmes d'assignation de fréquences, la segmentation, etc. Le Problème des Quatre Couleurs est l'un des problèmes importants parmi de nombreux problèmes de la théorie des graphes chromatiques, à partir duquel de nombreuses variantes et généralisations ont été proposées. Tout d'abord, dans cette thèse, nous visons à optimiser la stratégie de coloration des sommets de graphes et d'hypergraphes avec certaines contraintes données, en combinant le concept de coloration propre et d'élément représentatif de certains sous-ensembles de sommets. D'autre part, en fonction du sujet à colorer, une grande quantité de recherches et de problèmes de graphes à arêtes colorées ont émergé, avec des applications importantes en biologie et en technologies web. Nous fournissons quelques résultats analogues pour certaines questions de connectivité, afin de décrire des graphes dont les arêtes sont attribuées suffisamment de couleurs, garantissant ainsi des arbres couvrants ou des cycles ayant une structure chromatique spécifique<br>Graph colouring is one of the best known, popular and extensively researched subject in the field of graph theory, having a wide literature with approaches from many domains and a lot of problems, which are still open and studied by various mathematicians and computer scientists along the world. The Four Colour Problem, originating the study of graph colouring, was one of the central problem in graph theory in the last century, which asks if it is possible to colour every planar graph properly by four colours. Despite the theoretical origin, the graph colouring has found many applications in practice like scheduling, frequency assignment problems, segmentation, etc. The Four Colour Problem is a significant one among many problems in chromatic graph theory, from which many variants and generalizations have been proposed. Firstly, in this thesis, we aim to optimize the strategy to colour the vertex of graphs and hypergraphs with some given constraints, which combines the concept of proper colouring and representative element of some vertex subsets. On the other hand, according to the subject to be coloured, a large amount of research and problems of edge-coloured graphs have emerged, which have important applications to biology and web technologies. We provide some analogous results for some connectivity issues—to describe graphs whose edges are assigned enough colours, that guarantee spanning trees or cycles of a specific chromatic structure
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Weakly proper spanning tree"

1

"A Simple Algorithm to Find the Proper Spanning Tree in Metro Ethernet Networks." In International Conference on Software Technology and Engineering, 3rd (ICSTE 2011). ASME Press, 2011. http://dx.doi.org/10.1115/1.859797.paper27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Fatih Demiral, Mehmet. "Perspective Chapter: Experimental Analysis of Black Hole Algorithm with Heuristic Algorithms in Traveling Salesman Problem." In Response Surface Methods - Theory, Applications and Optimization Techniques [Working Title]. IntechOpen, 2024. http://dx.doi.org/10.5772/intechopen.1004380.

Full text
Abstract:
Black hole algorithm (BHA) is a popular metaheuristic algorithm proposed and applied for data clustering in 2013. BHA was applied to continuous and discrete problems; it is also hybridized with some algorithms in the literature. The pure BHA shows better performance than others in discrete optimization, such as traveling salesman problems. However, it requires improving the algorithm with competitive heuristics. Many heuristics have often been used to construct the initial tour of a salesman, such as the nearest neighbor algorithm (NN), nearest insertion algorithm (NI), cheapest insertion algorithm (CI), random insertion algorithm (RI), furthest insertion algorithm (FI), and minimal spanning tree algorithm (MST). In addition, the black hole algorithm is combined with popular heuristics, such as swap/or insert, reverse/or 2-opt swap, and swap-reverse/or 3-opt swap, and tested with proper parameters in this study. In the experimentation, classical datasets are used via TSP-library. The experimental results are given as best, average solutions/or deviations, and CPU time for all datasets. Besides, the hybrid algorithms demonstrate a better performance rate to get optimality. Finally, hybrid algorithms solve the discrete optimization problem in a short computing time for all datasets.
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Weakly proper spanning tree"

1

Srimani, Pradip K., and Zhenyu Xu. "Self-Stabilizing Algorithms of Constructing Spanning Tree and Weakly Connected Minimal Dominating Set." In 27th International Conference on Distributed Computing Systems Workshops (ICDCSW'07). IEEE, 2007. http://dx.doi.org/10.1109/icdcsw.2007.73.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Weakly proper spanning tree' for particular source types:
Journal articles
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!

To the bibliography