This paper proposes a hierarchical metaheuristic framework for optimally solving large-scale Euclidean Traveling Salesman Problems (TSP) that strategically embeds the clustered structure of input instances within crossed cubes interconnection networks to accelerate parallel optimization. The algorithm applies clustering-guided partitioning to hierarchically decompose TSP into compressed quadtree representations amenable to multi-level parallel evaluation across interconnected cores. An integrated ant colony-genetic algorithm then efficiently explores the partitioned solution space. Extensive experimentation demonstrates this structured mapping attains significant speedups under parallel execution versus congested sequential modes, with runtime scaling linearly in core count and sublinearly with problem size. Analysis reveals the hierarchical mapping attains optimized resource utilization and fault tolerance within crossed cubes to robustly handle problems an order of magnitude larger than prior work. This research thus presents an efficient approach for high-performance computing systems through aligning algorithmic and architectural hierarchies.
In the parallel processing field, graph embedding is motivated by simulation interconnection networks to another. The quadtree is an important technique used to present spatial data and is used in many application domains, especially computer vision and image processing. Researchers are interested in the construction and manipulation of quadtrees on parallel machines. The crossed cubes consider an alternative to the ordinary hypercube. It offers many attractive properties. Significantly, it reduces diameter by a factor of 2 that of the ordinary cubes. Moreover, the crossed cubes have a great capacity to simulate other architectures. This paper is interested in the one-by-one dilation two embedding of a particular sub-quadtree graph into m-dimensional crossed cubes.