The Connected P-Median Problem on Cactus Graphs

Area of Science:

• Operations Research
• Graph Theory
• Discrete Optimization

Background:

• The facility location problem is a critical area in operations research, focusing on optimal placement of services.
• The connected p-median problem specifically addresses scenarios where the located facilities must form a connected network.
• Cactus graphs, a specialized graph structure, are relevant in network design and analysis due to their unique properties.

Purpose of the Study:

• To develop an efficient algorithm for the connected p-median problem on weighted cactus graphs.
• To minimize the sum of weighted distances from all graph vertices to their nearest facility.
• To ensure the connectivity of the selected facility set (V).

Main Methods:

• The study focuses on a specific graph structure: cactus graphs with non-negative vertex and edge weights.
• An algorithm with a time complexity of O(n^2 * p^2) is proposed, where 'n' is the number of vertices and 'p' is the number of facilities.
• The methodology involves optimizing the placement of 'p' facilities to satisfy connectivity constraints and minimize total weighted distances.

Main Results:

• An efficient algorithm for the connected p-median problem on cactus graphs has been developed.
• The algorithm achieves a time complexity of O(n^2 * p^2), providing a significant improvement for certain problem instances.
• The solution guarantees that the induced subgraph formed by the 'p' facilities is connected.

Conclusions:

• The developed algorithm offers an effective solution for the connected p-median problem on weighted cactus graphs.
• This research contributes to the field of network optimization by providing a computationally feasible approach.
• The findings are applicable to real-world facility location scenarios requiring network connectivity.