The Two-Maxian Problem on Block Graphs with Distance Constraint

Abstract

This paper investigates the constrained two-maxian problem defined on block graphs, a special class of composite graphs containing trees and cacti as subclasses. The problem requires placing two facilities on a block graph such that the Euclidean/topological distance between the two facilities is bounded by a given upper limit, while maximizing the total weighted maximum distance from all client vertices to the farthest facility. We first analyze the structural properties of block graphs and the vertex optimality of the constrained two-maxian solution, proving that at least one facility in any optimal solution must be located at a vertex of the block graph. Based on this key property, we design an O(n4) time algorithm for the constrained two-maxian problem on block graphs. We further compare the proposed method with existing algorithms for trees and cycles and discuss a possible extension to cactus graphs.