A Solution of Degree Constrained Spanning Tree Using Hybrid GA
In real life, it is always an urge to reach our goal in minimum effort i.e., it should have a minimum constrained path. The path may be shortest route in practical life, either physical or electronic medium. The scenario is to represents the ambiance as a graph and to find a spanning tree with custom design criteria. Here, we have chosen a minimum degree spanning tree, which can be generated in real time with minimum turnaround time. The problem is NP-complete in nature [1, 2]. The solution approach, in general, is approximate. We have used a heuristic approach, namely hybrid genetic algorithm (GA), with motivated criteria of encoded data structures of graph. We compare the experimental result with the existing approximate algorithm and the result is so encouraging that we are interested to use it in our future applications.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems
Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios, often requiring intricate algorithmic design and exponential time. Recently, there has been growing interest in end-t…
Combinatorial OptimizationSteiner Tree ProblemSpanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate
We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph $G=(V,E)$ and a positive semi-definite matrix $\mathbf{A}$ indexed by $E$, a spanning-tree DPP defines a distribution such tha…
Point ProcessesNew characterizations of minimum spanning trees and of saliency maps based on quasi-flat zones
We study three representations of hierarchies of partitions: dendrograms (direct representations), saliency maps, and minimum spanning trees. We provide a new bijection between saliency maps and hierarchies based on quas…
Time Complexity Analysis of Evolutionary Algorithms for 2-Hop (1,2)-Minimum Spanning Tree Problem
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 o…
Combinatorial OptimizationEvolutionary AlgorithmsEvolutionary Diversity Optimization and the Minimum Spanning Tree Problem
In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Th…
DiversityEvolutionary Algorithms