This paper examines the concepts and practical applications of the spanning tree protocol (STP). It also covers per-VLAN spanning tree (PVST), multiple spanning tree (MST), and rapid STP (RSTP). ...Moreover, practical scenarios are presented to help the reader understand the concepts and implementations of these protocols. This study analyzes protocols using seven metrics. All protocols have been evaluated using these metrics in both small and big topology scenarios to obtain the best results. In addition, all metrics are mentioned in the introduction chapter, and the way used to apply tests on the metrics is described in the methodology chapter. Based on the experiments, different STPs performance are compared, including STP, RSTP, PVST, and MST. In summary, findings show that STP is easy to use and performs well overall, but it consistently has high latency issues. RSTP is suitable for small networks and has quick convergence, but it cannot handle as much load as STP. PVST performed the best in the experiments, as it demonstrated high scalability and the ability to handle a lot of pressure, although it requires strong hardware. However, MST did not perform as well as expected, as it struggled with delay problems and high jitter. In conclusion, it is recommended to use RSTP for simple networks that require fast convergence with dependable delay and capacity, or STP for networks that require good scaling and bandwidth. PVST is an excellent option for those who can afford high-performance hardware, while MST is suitable for simple networks or those with outdated hardware.
The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to ...theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop (1,2)-Minimum Spanning Tree problem (abbr. 2H-(1,2)-MSTP) in the context of evolutionary algorithms, which has been shown to be NP-hard. Following how evolutionary algorithms are applied to solve the MSTP, we first consider the evolutionary algorithms with search points in edge-based representation adapted to the 2H-(1,2)-MSTP (including the (1+1) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two variants). More specifically, we separately investigate the upper bounds on their expected time (i.e., the expected number of fitness evaluations) to obtain a 32-approximate solution with respect to different fitness functions. Inspired by the special structure of 2-hop spanning trees, we also consider the (1+1) EA with search points in vertex-based representation that seems not so natural for the problem and give an upper bound on its expected time to obtain a 32-approximate solution, which is better than the above mentioned ones.
Schmidt 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 important class of graphs by an ordinal function. Another largely open problem raised by Halin asks for a characterisation of the class of graphs with an end‐faithful spanning tree. A well‐studied subclass is formed by the graphs with a normal spanning tree. We determine a larger subclass, the class of normally traceable graphs, which consists of the connected graphs with a rayless tree‐decomposition into normally spanned parts. Investigating the class of normally traceable graphs further we prove that, for every normally traceable graph, having a rayless spanning tree is equivalent to all its ends being dominated. Our proofs rely on a characterisation of the class of normally traceable graphs by an ordinal rank function that we provide.
The Ordered Median Tree Location Problem Pozo, Miguel A.; Puerto, Justo; Torrejón, Alberto
Computers & operations research,
September 2024, 2024-09-00, Letnik:
169
Journal Article
Recenzirano
Odprti dostop
In this paper, we propose the Ordered Median Tree Location Problem (OMT). The OMT is a single-allocation facility location problem where p facilities must be placed on a network connected by a ...non-directed tree. The objective is to minimize the sum of the ordered weighted averaged allocation costs plus the sum of the costs of connecting the facilities in the tree. We present different MILP formulations for the OMT based on properties of the minimum spanning tree problem and the ordered median optimization. Given that ordered median location problems are rather difficult to solve we have improved the OMT solution performance by introducing covering variables in a valid reformulation plus developing two pre-processing phases to reduce the size of this formulations. In addition, we propose a Benders decomposition algorithm to approach the OMT. We establish an empirical comparison between these new formulations and we also provide enhancements that together with a proper formulation allow to solve medium size instances on general random graphs.
•The Ordered Median Tree Location Problem (OMT) is a new problem in the literature.•Several MILP formulations based on properties of the Minimum Spanning Tree Problem and the Ordered Median Optimization are presented.•Polyhedral description and comparison of the two main formulations are detailed.•A Benders decomposition and alternative formulation for the resolution are included.•Extensive computational results are provided.
A 4-approximation of the 2π3-MST Ashur, Stav; Katz, Matthew J.
Computational geometry : theory and applications,
January 2023, Letnik:
108
Journal Article
Recenzirano
Bounded-angle (minimum) spanning trees were first introduced in the context of wireless networks with directional antennas. They are reminiscent of bounded-degree (minimum) spanning trees, which have ...received significant attention. Let P be a set of n points in the plane, and let 0<α<2π be an angle. An α-spanning tree (α-ST) of P is a spanning tree of the complete Euclidean graph over P, with the following property: For each vertex pi∈P, the (smallest) angle that is spanned by all the edges incident to pi is at most α. An α-minimum spanning tree (α-MST) is an α-ST of P of minimum weight, where the weight of an α-ST is the sum of the lengths of its edges. In this paper, we consider the problem of computing an α-MST for the case where α=2π3. We present a 4-approximation algorithm, thus improving upon the previous results of Aschner and Katz and Biniaz et al., who presented algorithms with approximation ratios 6 and 163, respectively.
To obtain this result, we devise an O(n)-time algorithm that, given any Hamiltonian path Π of P, constructs a 2π3-ST T of P, such that T's weight is at most twice that of Π and, moreover, T is a 3-hop spanner of Π. This latter result is optimal (with respect to T's weight), since for any ε>0 there exists a polygonal path for which every 2π3-ST (of the corresponding set of points) has weight greater than 2−ε times the weight of the path.
Sebagai salah satu jenis UKM dibidang kuliner, Thai Tea Azka dihadapkan dengan berbagai persoalan optimalisasi manajemen sumber daya. Dalam persoalan penugasan karyawan Thai Tea Azka mengalami ...kendala dalam penempatan tiap karyawan karena belum memiliki jadwal yang jelas dan hanya didasarkan pada jarak yang ditempuh karyawan. Selain itu, Thai Tea Azka juga dihadapkan dengan berbagai kendala dalam pengiriman bahan baku. Olehnya itu penelitian ini bertujuan untuk mengetahui penempatan tugas karyawan dan rute pengiriman bahan baku pada UKM Thai Tea Azka. Pengumpulan data dalam penelitian ini dilakukan dengan teknik observasi dan wawancara terhadap pemilik dan beberapa karyawan. Data yang terkumpul, hasil penelitian menunjukan dianalisis dengan pendekatan model penugasan (Assignment method) dan model Jaringan (Networking method). Hasil analisis menunjukan bahwa penugasan karyawan dikatakan optimal karena setiap 1 karyawan menempati satu kedai pada tingkat biaya minimum. Kemudian rute pendistribusian bahan baku yang optimal di mulai dari cabang Kantor Kertanegara-Alfamart Sukahati-Pasar Haurgeulis-Alun-alun Haurgeulis-kemudian bisa memilih jalur ke arah Alfamart Nambo atau ke Pasar Wanguk, apabila memilih jalur ke Pasar Wanguk-Alfamart Gabus Pentil-Legok-babakan jaya kemudian kembali sampai cabang Alun-alun Haurgeulis ke arah Alfamart Nambo-Tugu Gantar dengan rute tempuh sebesar 38200meter atau 76400meter untuk pulang pergi
In chemical graph theory, various topological indices of the hexagonal lattices such as the energy, the numbers of perfect matchings and spanning trees, and so on, have been studied extensively. In ...this paper, we enumerate spanning trees with a perfect matching of the hexagonal lattices on the cylinder and Möbius strip.
Transmission in Certain Trees Sharon, Jane Olive; Rajalaxmi, T.M.
Procedia computer science,
2020, 2020-00-00, Letnik:
172
Journal Article
Recenzirano
Odprti dostop
Transmission of a vertex u in a graph G is defined as T(u) = ∑v∈V(G) d(u,v) 1. The expression T(G) = 1/2∑u,v∈V(G) d(u,v) is called the transmission of G. Further the cardinality of the set {T(u)/u ∈ ...V(G)} is addressed as the transmission dimension of G and is denoted by dimT(G) 5. Closeness centrality of a vertex v in G is defined as the reciprocal of the transmission of v. Using this centrality measure, the most important vertices in the graph are identified. In this paper we have computed the transmission of every vertex of an r-regular caterpillar and a spanning tree of the hypercube network.
PDF
