2025/10/20 by Alicia Muth, Muth, Alicia, E. Dov Neimand +1
Computer Science · #05C05 #05C12 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2510.18066
openalex publication_date 2025/10/20 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Expanding on the graph theoretic ideas of k-component order connectivity and distance-l domination, we present a quadratic-complexity algorithm that finds a tree's minimum failure-set cardinality, i.e., the minimum cardinality any subset of the tree's vertices must have so that all clusters of vertices further away than some l do not exceed a cardinality threshold. Applications of solutions to the expanded problems include choosing service center locations so that no large neighborhoods are excluded from service, while reducing the redundancy inherent in distance domination problems.