Optimizing Maximum Subgraph and Wirelength in WK-Recursive Networks
International Journal of Foundations of Computer Science · 16.07.2026 · 1-29
DOI: 10.1142/s0129054126500243 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 16.07.2026. Verfasst von P. Leo Joshwa und 3 weiteren Autor:innen.
Abstract (Originalsprache)
The Sierpiński network [Formula: see text] has become a prominent model for multiprocessor interconnection systems. Among hierarchical interconnection structures, the WK-recursive networks [Formula: see text] are notable for their advantageous properties, making them highly suitable for applications in parallel computing and VLSI design. These networks exhibit desirable features such as small diameter, high connectivity, and strong scalability. In this paper, we focus on solving the NP-complete Maximum Subgraph Problem (MSP) within the WK-recursive framework [Formula: see text], where [Formula: see text] and [Formula: see text]. We propose a computational method based on lexicographic ordering, implemented in SageMath, to determine the maximum number of edges that can be induced by any subset of [Formula: see text] vertices, for [Formula: see text]. Furthermore, we explore the Minimum Linear Arrangement (MinLA) problem by investigating embeddings of WK-recursive networks into host structures specifically path graphs, caterpillars, 1-hierarchical caterpillars, windmill, and necklace graph that aim to minimize total wirelength.
Zitieren
APA
Joshwa, P. L., Emilet, D. A., Rajalaxmi, T. M., & Rajan, R. S. (2026). Optimizing Maximum Subgraph and Wirelength in WK-Recursive Networks. International Journal of Foundations of Computer Science, 1-29. https://doi.org/10.1142/s0129054126500243
Vancouver
Joshwa PL, Emilet DA, Rajalaxmi TM, Rajan RS. Optimizing Maximum Subgraph and Wirelength in WK-Recursive Networks. International Journal of Foundations of Computer Science. 2026:1-29. doi:10.1142/s0129054126500243
BibTeX
@article{Joshwa2026,
author = {Joshwa, P. Leo and Emilet, D. Ahima and Rajalaxmi, T. M. and Rajan, R. Sundara},
title = {Optimizing Maximum Subgraph and Wirelength in WK-Recursive Networks},
journal = {International Journal of Foundations of Computer Science},
year = {2026},
pages = {1--29},
doi = {10.1142/s0129054126500243}
}
EUVIMED