A Generalization of Distance Domination
By: Alicia Muth, E. Dov Neimand
Potential Business Impact:
Finds best spots for services, avoiding big empty areas.
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.
Similar Papers
Elimination Distance to Dominated Clusters
Discrete Mathematics
Makes computer networks easier to manage.
Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
Distributed, Parallel, and Cluster Computing
Helps computers solve hard problems faster, with fewer mistakes.
Locating-dominating partitions for some classes of graphs
Combinatorics
Splits networks into two parts for better control.