# The ConnectedP-Median Problem on Cactus Graphs

Authors: Chunsong Bai; Jianjie Zhou; Zuosong Liang
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

This study deals with the facility location problem of locating a setVp of p facilities on a graph such that the subgraph induced by Vp is connected. We consider the connected p-median problem on a cactus graph G whose vertices and edges have nonnegative weights. The aim of a connected p-median problem is to minimize the sum of weighted distances from every vertex of a graph to the nearest vertex in Vp. We provide an On2p2 time algorithm for the connected p-median problem, where n is the number of vertices.


---

## Body

## 1. Introduction

Thep-median and p-center problems are central to the field of location theory and logistics and are now well studied in operations research. Applications of the two problems include the location of industrial plants, warehouses, distribution centers, and public service facilities in transportation networks, as well as the location of various facilities in telecommunication networks [1, 2].To determine the backup sites or to balance the workloads among the center vertices in real networks effectively, Yen and Chen [3] originally proposed the connected p-center problem and showed that the connected p-center problem is NP-hard on both bipartite graphs and split graphs. Yen [4] studied the connected p-center problem on block graphs. Bai et al. [5, 6] considered the connected p-center problem on cactus graphs and devised an On2p2 algorithm.Similar to the connectedp-center problem, Shan et al. [7] introduced the connected p-median problem and considered the connected p-median problems on interval and circular-arc graphs. Kang et al. [8] studied the connected p-median problem on block graphs and proved that the problem is linearly solvable on block graphs which have unit edge lengths.In this study, we consider the problem of finding the optimal location of connectedp-median on a cactus graph. The study is organized as follows. In the next section, we formally introduce the notations and the problem that we studied in this study. In Section 3, we study the connected p-median problem on a cactus graph and devise an algorithm with time complexity of On2p2. Finally, we conclude this study.


## 2. Problem Formulation

LetG=V,E,w,l be a connected graph with vertex set VV=n and edge set EV=n, where each vertex v∈V (or vi∈V) has a weight wv≥0 (or wi≥0) and each edge e∈E has a certain length le. For any two vertices u,v, let Pu,v be the shortest path from u to v, and du,v be the length of Pu,v. A p-vertex set Xp is called a connected p-vertex set if the induced subgraph of Xp is connected.A cycle is a sequencev1,…,vs,vs+1=v1 of ss≥3 clockwise indexed vertices, such that vi,vi+1 is an edge, 1≤i≤s. A graph G is called a cactus graph if any two cycles of G have at most one vertex in common. The vertex set of a cactus graph G can be divided into three disjoint subsets: G-vertices, C-vertices, and hinges. A vertex is called a C-vertex if it is in a cycle of G and its degree is 2 in G. A vertex is called a hinge if it is in a cycle of G and its degree is at least three. A vertex is called a G-vertex if it is not in a cycle of G.Given a cactus graphG, a subtree is a connected subgraph of G induced by some G-vertices and hinges that does not contain any cycle. A subtree is called as a graft if it is maximal and without two hinges belonging to the same cycle. A cycle or a graft is called a block of G.For convenience, we use a treeTG to represent the skeleton of G (Figure 1). Then, we convert TG into a rooted tree as follows: select an arbitrary block, e.g., B0, as the “root” of TG. For each vertex (block or hinge) v in TG, let levv be the level of v. Let Lm=maxv∈TGlevv be the maximal one of all levels. For each hinge h, by deleting the last edge of the path from B0 to h, we obtain two subtrees of TG. Let Gh be the subcacti of G induced by the vertices of h and all subcacti hanging from it, and let Ghc be the subcacti G−Gh. Note that the father of any block is always a hinge, which is called the block’s companion hinge. For simplicity, we choose an arbitrary vertex h0∈B0 as the virtual companion hinge of B0. Denote by Bh the block B if its companion hinge is h. Let GB,h be the subcactus of G induced by the vertices of Bh and all subcacti hanging from Bh, and let GB,hc be the subcacti G−GB,h. Specially, G=Gh0=GB0,h0 and Gh0c=GB0,h0c=∅.Figure 1
(a) A cactus graphG with five cycles C1,…,C5, three grafts G1,G2,G3, and six hinges h1,…,h6. (b) The tree structure TG of G.
(a)(b)For eachk-vertex set Xk in G, let FGXk be the sum of weighted distances from all vertices in G to Xk, that is,(1)FGXk=∑v∈VGwvdv,Xk,where dv,Xk=minxi∈Xkdv,xi.Problem 1.
Find a connectedp-vertex set Xp in G, such that FGXp is minimized. This problem is known as the connected p-median problem (CpM). The optimal solution Xp∗ is called a connected p-median of G.
Given a graftBh of G and an integer k, 1≤k≤p, for each vertex v∈Bh, the aim of the problem PGB,h,v,k is to find a connected k-vertex set VGB,h,v,k of GB,h, such that FGB,hVGB,h,v,k is minimized and v is the closest vertex to h in VGB,h,v,k∩VBh. We call the corresponding subset VGB,h,v,k as v-restricted connected k-median of GB,h.
Given a cycleBh of s indexed vertices v1=h,v2,…,vs and an integer k, 1≤k≤p, for any two vertices vi,vj⊂VBh, the aim of the problem PGB,h,vi,vj,k is to find a connected k-vertex set VGB,h,vi,vj,k of GB,h, such that FGB,hVGB,h,vi,vj,k is minimized and VGB,h,vi,vj,k∩VBh contains only the vertices of the path from vi to vj on Bh in clockwise direction. The corresponding subset VGB,h,vi,vj,k is called as vi,vj-restricted clockwise connected k-median of GB,h.
Given a subgraphGh and an integer k, 1≤k≤p for each hinge of Gh, the aim of the problem PGh,h,k is to find a connected k-vertex set VGh,h,k of Gh, such that FGhVGh,h,k is minimized. The corresponding subset VGh,h,kh-restricted is called as connected k-median of Gh.
For all subcactiGB,h of G, denote by V1 (respectively, V2) the possible v-restricted (vi,vj-restricted clockwise) connected p-medians VGB,h,v,p (respectively, VGB,h,vi,vj,p). For all hinges h of G, denote by V3 the possible h-restricted connected p-medians VGh,h,p. The following lemma establishes a significant relationship between the CpM problems on Gh0 and all restricted p-median problems.Lemma 1.
Given a cactus graphGh0, there exists a connected p-median Xp in V1∪V2∪V3.Proof.
Suppose thatv∈Xp is the closest vertex to h0 in G. Then, v could be a G-vertex, a C-vertex, or a hinge. We distinguish three cases.Case 1.
Given a graftBh of G and a G-vertex v of Bh, suppose that VGB,h,v,p is a v-restricted connected p-median of GB,h, then VGB,h,v,p is a feasible solution to the CpM problem, that is,(2)FGVGB,h,v,p≥FGXp.
On the other hand, sinceXp is also a v-restricted connected p-vertex of GB,h, we have(3)FGXp=FGB,hXp+∑u∈VGB,hcwudu,h+dh,v≥FGB,hVGB,h,v,p+∑u∈VGB,hcwudu,h+dh,v=FGVGB,h,v,p.
Thus,FGXp=FGVGB,h,v,p, which means VGB,h,v,p is a connected p-median of Gh0.Case 2.
Given a cycleBh of G and two C-vertices vi,vj of Bh, i≤j. Suppose that Xp∩VBh includes only the vertices of the path from vi to vj on Bh in clockwise direction, and VGB,h,vi,vj,p is a vi,vj-restricted clockwise connected p-median of GB,h. Similar as Case 1, we deduce that(4)FGVGB,h,vi,vj,p≥FGXp,FGXp=FGB,hXp+∑u∈VGB,hcwudu,h+mindh,vi,dh,vj≥FGB,hVGB,h,vi,vj,p+∑u∈VGB,hcwudu,h+mindh,vi,dh,vj=FGVGB,h,vi,vj,p.
Thus,FGXp=FGVGB,h,vi,vj,p, VGB,h,vi,vj,p is a connected p-median of Gh0.Case 3.
For the casev=h is a hinge, we distinguish three subcases.Subcase 3.1. The neighbor ofh is a graft Bh. We can obtain FGXp=FGVGB,h,h,p and VGB,h,h,p is a connected p-median of Gh0 through the same discussion as in Case 1.Subcase 3.2. The neighbor ofh is a cycle Bh, and Xp∩VBh includes the vertices of the path from vi to vj on Bh in clockwise direction, i≤j. We can obtain FGXp=FGVGB,h,vi,vj,p and VGB,h,vi,vj,p is a connected p-median of Gh0 through the same discussion as in Case 2.Subcase 3.3. The neighbor ofh belongs to more than one block. Assume that VGh,h,p is a h-restricted connected p-median of Gh. Similar as Case 1, we deduce that(5)FGVGh,h,p≥FGXp,FGXp=FGhXp+∑u∈VGhcwudu,h≥FGhVGh,h,p+∑u∈VGhcwudu,h=FGVGh,h,p.
Thus,FGXp=FGVGh,h,p, and VGh,h,p is a connected p-median of Gh0.
From the discussion above, there exists a vertex-restricted connectedp-median whose sum of weighted distances of Gh0 is equal to the sum of weighted distances of a connected p-median of Gh0.
In view of Lemma1, we will design an algorithm to find all the restricted connected p-medians in V1∪V2∪V3. The algorithm uses the idea of dynamic programming. Traverse the tree TG “upward,” from the vertices (block or hinge) with higher levels to the vertices with lower levels. An arbitrary order is defined when vertices are with the same levels. In each loop, we select a block Bh or a hinge h. If Bh is a graft, we calling program GRAFT B,h to deal with the problem on GB,h; otherwise, we call program CYCLE B,h. When it comes to Gh, we call program HINGE G,h. For the further computations, all useful data are transferred to h. When the block Bh0 has been checked, these data can be used to find a connected p-median Vp∗ of G.


## 3. Algorithm for the CpM Problem on Cactus Graph

### 3.1. The Program GRAFT (B,h)

In this subsection, for each graftBh of G and each possible positive integer k, our task is to find all restricted connected k-medians VGB,h,v,k.Denote byT the given graft Bh. Assume that T is rooted at the hinge h. Denote by L′=maxv∈VTlevv. For each vertex v≠h, we can obtain two subtrees of T by deleting the last edge of the path from h to v. Let Tv be the subtree that contains v, and let Tvc=T−Tv. Let GB,v and GB,hc=GB,h−Gv be the subgraphs of Gh corresponding to Tv and Tvc, respectively.For each vertexv∈T, let Ev be the edges of Tv that are incident with v, and let sv=Ev. After sorting the edges of Ev in an arbitrary order, the lth edge is denoted by ev,l. If ev,l=v,vl, then v is called as the farther farvl of vl and vl is called as the lthson of v. Let sonv be all sons of v. For the subtree Tv, let Tev,l be the maximal connected subtree that contains v but not any edge ev,j for j>l. Particularly, Tev,0=v and Tev,sv=Tv.For the subgraphGB,v, let GB,ev,l be the subgraph induced by all vertices of Tev,l and all subcacti hanging from it. For the subgraph GB,ev,l, let Vev,l,k be the connected k-vertex set that contains v but not any vertex vj∈sonv for j>l. We define the sum of weighted distances of Vev,l,k over GB,ev,l as follows.Definition 1.
Given a subgraphGB,ev,l, the optimal value of Vev,l,k is defined as(6)f∗Vev,l,k=minVev,l,k⊆GB,ev,lfGB,ev,lVev,l,k,where 1≤k≤minp,GB,ev,l. Let V∗ev,l,k be the corresponding set to f∗Vev,l,k.
Once we obtain all valuesf∗Vev,sv,k and fGB,vcv, the sum of weighted distances from vertices in GB,h to VGB,h,v,k can be calculated as(7)FGB,hVGB,h,v,k=f∗Vev,sv,k+fGB,vcv.
For the blockBh, we first deal with all vertices in leafT. For each G-vertex v∈leafT, let(8)f∗Vev,0,1=0,V∗ev,0,1=v.
For each hinge vertexv∈leafT, let(9)WGB,v=WGv,f∗Vev,0,k=FGvVGv,v,k,V∗ev,0,k=VGv,v,k.


#### 3.1.1. The Calculation off∗Vev,l,k and V∗ev,l,k

Suppose that, when the phasej begins, all values f∗Vev,sv,k have been calculated for each vertex v with level levv≥L′−j+1 in T. In the phase j, we search for all vertices of level L′−j. For each of these vertices v, we first calculate all values f∗ev,sv,k by the following method, and then, go to the next vertex with level L′−j. If v is a G-vertex or v=h, we start by assigning(10)WGB,v=wv+∑u∈sonvWGB,u,f∗Vev,0,1=∑u∈sonvf∗Veu,0,1+WGB,ulv,u.Ifv is a hinge such that v≠h, we start by assigning(11)WGB,v=WGv+∑u∈sonvWGB,u,f∗Vev,0,1=FGvVGv,v,1+∑u∈sonvf∗Veu,0,1+WGB,ulv,u.Assuming that, for alll′<l, the values f∗Vev,l′,k have been calculated. Then, the value f∗Vev,l,k can be calculated as follows:(12)f∗Vev,l,k=minmin1≤k′≤k−1f∗Vev,l−1,k′+f∗Vevl,svl,k−k′,f∗Vev,l−1,k+f∗Vevl,svl,1+WGB,vllv,vl.For the right side of the above formula, the minimal value of the set inside corresponds to the casevl∈V∗ev,l,k, while the value behind corresponds to the case vl∉V∗ev,l,k (Figure 2).Figure 2
The subgraphsGB,ev,l−1 and GB,vl of GB,v.Ifvl∈V∗ev,l,k, set(13)V∗ev,l,k=V∗ev,l−1,k″∪V∗evl,svl,k−k″,where V∗ev,l−1,k″ and V∗evl,svl,k−k″ are the corresponding subsets to f∗Vev,l−1,k″ and f∗Vevl,svl,k−k″, respectively. Otherwise, set(14)V∗ev,l,k=V∗ev,l−1,k.Note that there are at mostVTp values f∗Vev,l,k which can be calculated by traversing the edges in T. Each calculation contains finding the minimum in at most 2k terms. Then, all the values f∗Vev,l,k can be computed in OVTp2 time.


#### 3.1.2. The Calculation offGB,vcv

We start by assigningfGB,hch=0. Suppose that, for all vertices v with level levv<j in T, all values fGB,vcv have been calculated when the phase j begins. In the phase j, we traverse all vertices of level j. For each of these vertex v, we set WGB,vc=WGB,h−WGB,v and compute fGB,vcv as follows:(15)fGB,vcv=fGB,farvcfarv+f∗Vefarv,sfarv,1−f∗Vev,sv,1−WGB,vlv,farv+WGB,vclv,farv.After all valuesf∗Vev,l,k have been calculated, all values fGB,vcv can be calculated by traversing vertices in T “downward.” The total calculations take OVT time. Then, all values FGB,hVGB,h,v,k can be computed by formula (7) in OVTp2 time.


### 3.2. The Program CYCLE (B,h)

In this subsection, we are given a cycleBh and the relevant subcactus GB,h; for all pairs vi,vj⊂Bh and all possible positive numbers k, our task is to find all restricted connected k-medians VGB,h,vi,vj,k.Denote byC the Bh. Assume that Cv1=h,v2,…,vt, and all vertices are indexed in clockwise. For each vertex vi in C, let GB,v1=v1, where GB,vi be the subgraph that contains vi and all subcacti hanging from it, 2≤i≤s. For any pair vi,vj∈VC,i≤j, let Cvi,vjCvi,vjco be the subgraph induced by all vertices of the path from vi to vj in clockwise (counter-clockwise) direction. Let GB,vi,vjGB,vi,vjco be the subgraph induced by Cvi,vjCvi,vjco and all subcacti hanging from it, and let GB,vi,vjc=GB,v1,vt−Gvi,vj. The calculation of VGB,h,vi,vj,k. Given a pair vi,vj and a integer k, denote by Vvi,vj,k the connected k-vertex set in GB,vi,vj that includes vi and vj. For each integer k, 1≤k≤minp,GB,,vi,vj, and the sum of the weighted distances of Vvi,vj,k over GB,vi,vj is defined as(16)f1∗Vvi,vj,k=minVvi,vj,k⊆GB,vi,vjFGB,vi,vjVvi,vj,k.LetV∗vi,vj,k be the corresponding set to f1∗Vvi,vj,k.Suppose that the midpoint of the pathCvj,vi lies in the edge emj,i. In particular, if the midpoint is a vertex, assume it coincides with vmj,i. By deleting emj,i from GB,vi,vjc, we obtain two subgraphs GB,vi,vjc,1 and GB,vi,vjc,2, which contain vmj,i and vmj,i+1, respectively. Next, we define(17)f2∗Vvi,vj,k=∑u∈VGB,vi,vjc,1WGB,udu,vj,f3∗Vvi,vj,k=∑u∈VGvi,vjc,2WGB,udu,vi,to denote the partial sum of the weighted distances to vj and vi, respectively.Once all the values defined above have been computed, we can calculate the sum of the weighted distances ofVGB,h,vi,vj,k:(18)FGB,hVGB,h,vi,vj,k=f1∗Vvi,vj,k+f2∗Vvi,vj,k+f3∗Vvi,vj,k.We assignVGB,h,vi,vj,k=V∗vi,vj,k.Given a vertexvi of C. If vi is a C-vertex or vi=h, we start by assigning(19)WGB,vi=wvi,f1∗Vvi,vi,1=0.Ifvi is a hinge that is not equal to h, we start by assigning(20)WGB,vi=WGvi,f1∗Vvi,vi,1=FGviVGvi,vi,1.SinceCvi,vj is a graft, for all j≥i and possible numbers k, the values f1∗Vvi,vj,k can be calculated by running GRAFT B,h on GB,vi,vj. The computation of the values f1∗Vvi,vj,k for all vertices vi and vj of C takes OVC2p2 time.For the sake of simplicity, we only describe the calculation off2∗Vvi,vj,k, while the values of f3∗Vvi,vj,k can be calculated in a similar way.Note that, for all pairvi,vj of C, the corresponding middle edges can be found by the method similar as in [5] in OVC2 time. For each edge em=vm,vm+1 of C, denote by Pem=vr1,vl1,vr2,vl2,…,vrt,vlt all pairs of vertices of C whose middle edge is em, where l1≥l2≥⋯≥lt. Let V=vl1,vl2,…,vlt.By traversing all vertices inV, for l1≥lk≥lt, all values f2∗Vvrk,vlk,k can be calculated by the following formula:(21)f2∗Vvrk,vlk,k=f2∗Vvrk−1,vlk−1,k+WGB,vlk−1,vmdvlk−1,vlk+∑lk>j′>lk−1f1∗Vvj′,vj′,1+WGB,vj′dvj′,vlk,in OVC time. Thus, the calculation of all values f2∗Vvi,vj,k takes OVC2 time.Last, the valueWGB,h is reassigned as WGB,h=∑vi∈BhWGB,vi, which can be computed in OVC time. Then, all the values FGB,hVGB,h,vi,vj,k can be computed by formula (18) in OVC2p2 time.


### 3.3. The Program HINGEGh,h

In this subsection, we are given a hingeh and the relevant subcactus Gh; for all possible positive integers k, our task is to find the restricted connected k-medians VGh,h,k.Assume thath is a hinge of G. If h is the hinge of the block Bi with a lower level in TG, then we call h as the farther farBi of Bi and Bi as the son of h. Let sonh be all sons of h and sh=Eh. Let Eh be all edges that incident with h. By sorting all edges of Eh in an arbitrary order, the lth edge is denoted as eh,l. For each subgraph Gh, denote by Geh,l the maximal connected subgraph that contains h and all subcacti hanging from it but not any block Bj for j>l. Particularly, Geh,0=h and Geh,sh=Gh (Figure 3).Figure 3
The local structure ofGh in TG.For each subgraphGeh,l, denote by Veh,l,k the connected k-vertex set that contains h but not any vertex of Bj∈sonh for j>l. Next, we define the optimal value of Veh,l,k over Geh,l.Definition 2.
In subgraphGeh,l, define(22)f∗Veh,l,k=minVeh,l,k⊆Geh,lfGeh,lVeh,l,k,where 1≤k≤minp,Geh,l. Let V∗eh,l,k be the corresponding set to f∗Veh,l,k.
Once we obtain the valuesf∗eh,sh,k, the sum of weighted distances from vertices of Gh to VGh,h,k can be calculated as(23)FGhVGh,h,k=f∗eh,sh,k.
We assignVGh,h,k=V∗eh,sh,k.
According to our assumption, we obtain(24)f∗Veh,0,1=∑graftBi∈sonhFGBi,hVGBi,h,h,1+∑cycleBj∈sonhFGBj,hVGBj,h,h,h,1,and assign(25)V∗eh,0,1=h.


#### 3.3.1. The Calculation off∗Veh,l,k and V∗eh,l,k

Suppose that, when the phasej begins, the value FGBi,hVGBi,h,h,1 or FGBi,hVGBi,h,h,h,1 has been calculated for each block Bi∈TG of level levBi≥Lm−j+1. In the phase j, we search all hinges of level Lm−j. For each of these hinges h, we calculate all values f∗Veh,sh,k by the following method, and then, go to the next hinge with level Lm−j.Assuming that, for alll′<l, the values f∗Veh,l′,k have been calculated. Then, the value f∗Veh,l,k can be calculated as follows:(26)f∗Veh,l,k=min1≤k′≤k−1f∗Veh,l−1,k′+FGBl,hVGBl,h,h,k−k′,if Bl is graft, otherwise,(27)f∗Veh,l,k=min1≤k′≤k−1f∗Veh,l−1,k′+FGBl,hVGBl,h,h,h,k−k′.IfBl is graft, set(28)V∗eh,l,k=V∗eh,l−1,k′∪VGBl,h,h,k−k′,otherwise, set(29)V∗eh,l,k=V∗eh,l−1,k′∪VGBl,h,h,h,k−k′,where V∗eh,l−1,k′, VGBl,h,h,k−k′, and VGBl,h,h,h,k−k′ are the corresponding sets to f∗Veh,l−1,k′, FGBl,hVGBl,h,h,k−k′, and FGBl,hVGBl,h,h,h,k−k′, respectively.There are at mostVTGp values f∗Veh,l,k which can be calculated by traversing the edges in TG. Each calculation contains finding the minimum in at most 2k terms. Then, all the values f∗Veh,l,k can be computed in OVTGp2 time.Last,WGh is assigned as WGh=∑Bi∈sonhWGBi,h−whsh−1, which takes constant time.


### 3.4. The Procedure HINGEGhc,h

In this subsection, given a hingeh and the relevant subcactus Ghc, our task is to calculate the sum of weighted distances from vertices in Ghcs to h and the total weights of Ghc.


#### 3.4.1. The Calculation ofFGhch and WGhc

We start by assigningWGB,h0c=0 and FGB,h0ch0=0. Suppose that, when the phase j begins, the value of FGhch and WGhc has been calculated for each hinge h∈TG with level levh<j. In the phase j, we search all hinges of level j. For each of these hinges h, set(30)WGhc=WGh0−WGh.Suppose thatfarh=B′ in TG and the hinge of B′ is h′ (Figure 3). Then, FGhch can be computed as follows:(31)FGhch=FGh′ch′+WGh′cdh′,h+FGB′,h′VGB′,h′,h,1−FGhVGh,h,1,if B′ is a graft, otherwise,(32)FGhch=FGh′ch′+WGh′cdh′,h+FGB′,h′VGB′,h′,h,h,1−FGhVGh,h,1.Note that all valuesFGhch and WGhc can be calculated by traversing all vertices of TG “downward.” The total calculations take OVTG time.


### 3.5. Algorithm for the CpM Problem

According to Lemma1, we can find a connected p median Vp∗ from V1∪V2∪V3. The sum of weighted distance from vertices of G to Xp∗ can be calculated as(33)FGVp∗=minminVGB,h,v,p∈V1FGB,hVGB,h,v,p+FGhch+WGhcdh,v,minVGB,h,vi,vj,p∈V2FGB,hVGB,h,vi,vj,p+FGhch+WGhcmindh,vi,dh,vj,minVGh,h,p∈V3FGhVGh,h,p+FGhch.Next, we design Algorithm1 to solve the CpM problem. For a given cactus graph G, as a preprocessing of Algorithm 1, first, the distance-matrix of the cactus will be calculated. Then, we construct the rooted skeleton graph of the cactus and calculate maximum level Lm. This preprocessing will be finished in On2 time.Algorithm 1: An algorithm for the connected p-median problem of cactus graphs.
Input: A cactus graph G, the corresponding rooted skeleton TG, and the maximum level LmOutput: A connected p median Vp∗ and the sum of weighted distance to Vp∗(1)
SetV1=V2=V3=∅(2)
fori=Lm;i≥0;i−do(3)
for vertex v∈TG with levv=ido(4)
ifv represents a graft Bthen(5)
Find the companion hinge ofB in TG, assuming it to h, and calculate the level L′(6)
CallGRAFTB,h to calculate the values FGB,hVGB,h,v,k and find VGB,h,v,k for v∈Bh of level j and all possible integers k, and set V1=V1+VGB,h,v,p.(7)
end(8)
ifv represent a cycle Bthen(9)
Find the companion hinge ofB in TG, assuming it to h(10)
CallCYCLEB,h to calculate the values FGB,hVGB,h,vi,vj,k and find VGB,h,vi,vj,k for vi,vj⊂VB of i≤j and all possible integers k, and set V2=V2+VGB,h,vi,vj,p.(11)
end(12)
ifv represents a hinge hthen(13)
CallHINGEGh,h to calculate the values FGhVGh,h,k and find VGh,h,k for all possible integers k, and set V3=V3+VGh,h,p.(14)
end(15)
end(16)
end(17)
fori=0;i≤Lm−1;i++do(18)
CallHINGEGhc,h to calculate the values FGhch and WGhc for each hinge h of levh=i(19)
end(20)
return use formula (33) to calculate FGVp∗ and find a connected p-median Xp∗.Since there are at mostOn2 elements in V1∪V2∪V3, the calculation of FGVp∗ takes On2 time. Then, we can use the following theorem to end this section.Theorem 1.
On the cactus graph withn vertices, the CpM problem can be solved in On2p2 time.


## 3.1. The Program GRAFT (B,h)

In this subsection, for each graftBh of G and each possible positive integer k, our task is to find all restricted connected k-medians VGB,h,v,k.Denote byT the given graft Bh. Assume that T is rooted at the hinge h. Denote by L′=maxv∈VTlevv. For each vertex v≠h, we can obtain two subtrees of T by deleting the last edge of the path from h to v. Let Tv be the subtree that contains v, and let Tvc=T−Tv. Let GB,v and GB,hc=GB,h−Gv be the subgraphs of Gh corresponding to Tv and Tvc, respectively.For each vertexv∈T, let Ev be the edges of Tv that are incident with v, and let sv=Ev. After sorting the edges of Ev in an arbitrary order, the lth edge is denoted by ev,l. If ev,l=v,vl, then v is called as the farther farvl of vl and vl is called as the lthson of v. Let sonv be all sons of v. For the subtree Tv, let Tev,l be the maximal connected subtree that contains v but not any edge ev,j for j>l. Particularly, Tev,0=v and Tev,sv=Tv.For the subgraphGB,v, let GB,ev,l be the subgraph induced by all vertices of Tev,l and all subcacti hanging from it. For the subgraph GB,ev,l, let Vev,l,k be the connected k-vertex set that contains v but not any vertex vj∈sonv for j>l. We define the sum of weighted distances of Vev,l,k over GB,ev,l as follows.Definition 1.
Given a subgraphGB,ev,l, the optimal value of Vev,l,k is defined as(6)f∗Vev,l,k=minVev,l,k⊆GB,ev,lfGB,ev,lVev,l,k,where 1≤k≤minp,GB,ev,l. Let V∗ev,l,k be the corresponding set to f∗Vev,l,k.
Once we obtain all valuesf∗Vev,sv,k and fGB,vcv, the sum of weighted distances from vertices in GB,h to VGB,h,v,k can be calculated as(7)FGB,hVGB,h,v,k=f∗Vev,sv,k+fGB,vcv.
For the blockBh, we first deal with all vertices in leafT. For each G-vertex v∈leafT, let(8)f∗Vev,0,1=0,V∗ev,0,1=v.
For each hinge vertexv∈leafT, let(9)WGB,v=WGv,f∗Vev,0,k=FGvVGv,v,k,V∗ev,0,k=VGv,v,k.


### 3.1.1. The Calculation off∗Vev,l,k and V∗ev,l,k

Suppose that, when the phasej begins, all values f∗Vev,sv,k have been calculated for each vertex v with level levv≥L′−j+1 in T. In the phase j, we search for all vertices of level L′−j. For each of these vertices v, we first calculate all values f∗ev,sv,k by the following method, and then, go to the next vertex with level L′−j. If v is a G-vertex or v=h, we start by assigning(10)WGB,v=wv+∑u∈sonvWGB,u,f∗Vev,0,1=∑u∈sonvf∗Veu,0,1+WGB,ulv,u.Ifv is a hinge such that v≠h, we start by assigning(11)WGB,v=WGv+∑u∈sonvWGB,u,f∗Vev,0,1=FGvVGv,v,1+∑u∈sonvf∗Veu,0,1+WGB,ulv,u.Assuming that, for alll′<l, the values f∗Vev,l′,k have been calculated. Then, the value f∗Vev,l,k can be calculated as follows:(12)f∗Vev,l,k=minmin1≤k′≤k−1f∗Vev,l−1,k′+f∗Vevl,svl,k−k′,f∗Vev,l−1,k+f∗Vevl,svl,1+WGB,vllv,vl.For the right side of the above formula, the minimal value of the set inside corresponds to the casevl∈V∗ev,l,k, while the value behind corresponds to the case vl∉V∗ev,l,k (Figure 2).Figure 2
The subgraphsGB,ev,l−1 and GB,vl of GB,v.Ifvl∈V∗ev,l,k, set(13)V∗ev,l,k=V∗ev,l−1,k″∪V∗evl,svl,k−k″,where V∗ev,l−1,k″ and V∗evl,svl,k−k″ are the corresponding subsets to f∗Vev,l−1,k″ and f∗Vevl,svl,k−k″, respectively. Otherwise, set(14)V∗ev,l,k=V∗ev,l−1,k.Note that there are at mostVTp values f∗Vev,l,k which can be calculated by traversing the edges in T. Each calculation contains finding the minimum in at most 2k terms. Then, all the values f∗Vev,l,k can be computed in OVTp2 time.


### 3.1.2. The Calculation offGB,vcv

We start by assigningfGB,hch=0. Suppose that, for all vertices v with level levv<j in T, all values fGB,vcv have been calculated when the phase j begins. In the phase j, we traverse all vertices of level j. For each of these vertex v, we set WGB,vc=WGB,h−WGB,v and compute fGB,vcv as follows:(15)fGB,vcv=fGB,farvcfarv+f∗Vefarv,sfarv,1−f∗Vev,sv,1−WGB,vlv,farv+WGB,vclv,farv.After all valuesf∗Vev,l,k have been calculated, all values fGB,vcv can be calculated by traversing vertices in T “downward.” The total calculations take OVT time. Then, all values FGB,hVGB,h,v,k can be computed by formula (7) in OVTp2 time.


## 3.1.1. The Calculation off∗Vev,l,k and V∗ev,l,k

Suppose that, when the phasej begins, all values f∗Vev,sv,k have been calculated for each vertex v with level levv≥L′−j+1 in T. In the phase j, we search for all vertices of level L′−j. For each of these vertices v, we first calculate all values f∗ev,sv,k by the following method, and then, go to the next vertex with level L′−j. If v is a G-vertex or v=h, we start by assigning(10)WGB,v=wv+∑u∈sonvWGB,u,f∗Vev,0,1=∑u∈sonvf∗Veu,0,1+WGB,ulv,u.Ifv is a hinge such that v≠h, we start by assigning(11)WGB,v=WGv+∑u∈sonvWGB,u,f∗Vev,0,1=FGvVGv,v,1+∑u∈sonvf∗Veu,0,1+WGB,ulv,u.Assuming that, for alll′<l, the values f∗Vev,l′,k have been calculated. Then, the value f∗Vev,l,k can be calculated as follows:(12)f∗Vev,l,k=minmin1≤k′≤k−1f∗Vev,l−1,k′+f∗Vevl,svl,k−k′,f∗Vev,l−1,k+f∗Vevl,svl,1+WGB,vllv,vl.For the right side of the above formula, the minimal value of the set inside corresponds to the casevl∈V∗ev,l,k, while the value behind corresponds to the case vl∉V∗ev,l,k (Figure 2).Figure 2
The subgraphsGB,ev,l−1 and GB,vl of GB,v.Ifvl∈V∗ev,l,k, set(13)V∗ev,l,k=V∗ev,l−1,k″∪V∗evl,svl,k−k″,where V∗ev,l−1,k″ and V∗evl,svl,k−k″ are the corresponding subsets to f∗Vev,l−1,k″ and f∗Vevl,svl,k−k″, respectively. Otherwise, set(14)V∗ev,l,k=V∗ev,l−1,k.Note that there are at mostVTp values f∗Vev,l,k which can be calculated by traversing the edges in T. Each calculation contains finding the minimum in at most 2k terms. Then, all the values f∗Vev,l,k can be computed in OVTp2 time.


## 3.1.2. The Calculation offGB,vcv

We start by assigningfGB,hch=0. Suppose that, for all vertices v with level levv<j in T, all values fGB,vcv have been calculated when the phase j begins. In the phase j, we traverse all vertices of level j. For each of these vertex v, we set WGB,vc=WGB,h−WGB,v and compute fGB,vcv as follows:(15)fGB,vcv=fGB,farvcfarv+f∗Vefarv,sfarv,1−f∗Vev,sv,1−WGB,vlv,farv+WGB,vclv,farv.After all valuesf∗Vev,l,k have been calculated, all values fGB,vcv can be calculated by traversing vertices in T “downward.” The total calculations take OVT time. Then, all values FGB,hVGB,h,v,k can be computed by formula (7) in OVTp2 time.


## 3.2. The Program CYCLE (B,h)

In this subsection, we are given a cycleBh and the relevant subcactus GB,h; for all pairs vi,vj⊂Bh and all possible positive numbers k, our task is to find all restricted connected k-medians VGB,h,vi,vj,k.Denote byC the Bh. Assume that Cv1=h,v2,…,vt, and all vertices are indexed in clockwise. For each vertex vi in C, let GB,v1=v1, where GB,vi be the subgraph that contains vi and all subcacti hanging from it, 2≤i≤s. For any pair vi,vj∈VC,i≤j, let Cvi,vjCvi,vjco be the subgraph induced by all vertices of the path from vi to vj in clockwise (counter-clockwise) direction. Let GB,vi,vjGB,vi,vjco be the subgraph induced by Cvi,vjCvi,vjco and all subcacti hanging from it, and let GB,vi,vjc=GB,v1,vt−Gvi,vj. The calculation of VGB,h,vi,vj,k. Given a pair vi,vj and a integer k, denote by Vvi,vj,k the connected k-vertex set in GB,vi,vj that includes vi and vj. For each integer k, 1≤k≤minp,GB,,vi,vj, and the sum of the weighted distances of Vvi,vj,k over GB,vi,vj is defined as(16)f1∗Vvi,vj,k=minVvi,vj,k⊆GB,vi,vjFGB,vi,vjVvi,vj,k.LetV∗vi,vj,k be the corresponding set to f1∗Vvi,vj,k.Suppose that the midpoint of the pathCvj,vi lies in the edge emj,i. In particular, if the midpoint is a vertex, assume it coincides with vmj,i. By deleting emj,i from GB,vi,vjc, we obtain two subgraphs GB,vi,vjc,1 and GB,vi,vjc,2, which contain vmj,i and vmj,i+1, respectively. Next, we define(17)f2∗Vvi,vj,k=∑u∈VGB,vi,vjc,1WGB,udu,vj,f3∗Vvi,vj,k=∑u∈VGvi,vjc,2WGB,udu,vi,to denote the partial sum of the weighted distances to vj and vi, respectively.Once all the values defined above have been computed, we can calculate the sum of the weighted distances ofVGB,h,vi,vj,k:(18)FGB,hVGB,h,vi,vj,k=f1∗Vvi,vj,k+f2∗Vvi,vj,k+f3∗Vvi,vj,k.We assignVGB,h,vi,vj,k=V∗vi,vj,k.Given a vertexvi of C. If vi is a C-vertex or vi=h, we start by assigning(19)WGB,vi=wvi,f1∗Vvi,vi,1=0.Ifvi is a hinge that is not equal to h, we start by assigning(20)WGB,vi=WGvi,f1∗Vvi,vi,1=FGviVGvi,vi,1.SinceCvi,vj is a graft, for all j≥i and possible numbers k, the values f1∗Vvi,vj,k can be calculated by running GRAFT B,h on GB,vi,vj. The computation of the values f1∗Vvi,vj,k for all vertices vi and vj of C takes OVC2p2 time.For the sake of simplicity, we only describe the calculation off2∗Vvi,vj,k, while the values of f3∗Vvi,vj,k can be calculated in a similar way.Note that, for all pairvi,vj of C, the corresponding middle edges can be found by the method similar as in [5] in OVC2 time. For each edge em=vm,vm+1 of C, denote by Pem=vr1,vl1,vr2,vl2,…,vrt,vlt all pairs of vertices of C whose middle edge is em, where l1≥l2≥⋯≥lt. Let V=vl1,vl2,…,vlt.By traversing all vertices inV, for l1≥lk≥lt, all values f2∗Vvrk,vlk,k can be calculated by the following formula:(21)f2∗Vvrk,vlk,k=f2∗Vvrk−1,vlk−1,k+WGB,vlk−1,vmdvlk−1,vlk+∑lk>j′>lk−1f1∗Vvj′,vj′,1+WGB,vj′dvj′,vlk,in OVC time. Thus, the calculation of all values f2∗Vvi,vj,k takes OVC2 time.Last, the valueWGB,h is reassigned as WGB,h=∑vi∈BhWGB,vi, which can be computed in OVC time. Then, all the values FGB,hVGB,h,vi,vj,k can be computed by formula (18) in OVC2p2 time.


## 3.3. The Program HINGEGh,h

In this subsection, we are given a hingeh and the relevant subcactus Gh; for all possible positive integers k, our task is to find the restricted connected k-medians VGh,h,k.Assume thath is a hinge of G. If h is the hinge of the block Bi with a lower level in TG, then we call h as the farther farBi of Bi and Bi as the son of h. Let sonh be all sons of h and sh=Eh. Let Eh be all edges that incident with h. By sorting all edges of Eh in an arbitrary order, the lth edge is denoted as eh,l. For each subgraph Gh, denote by Geh,l the maximal connected subgraph that contains h and all subcacti hanging from it but not any block Bj for j>l. Particularly, Geh,0=h and Geh,sh=Gh (Figure 3).Figure 3
The local structure ofGh in TG.For each subgraphGeh,l, denote by Veh,l,k the connected k-vertex set that contains h but not any vertex of Bj∈sonh for j>l. Next, we define the optimal value of Veh,l,k over Geh,l.Definition 2.
In subgraphGeh,l, define(22)f∗Veh,l,k=minVeh,l,k⊆Geh,lfGeh,lVeh,l,k,where 1≤k≤minp,Geh,l. Let V∗eh,l,k be the corresponding set to f∗Veh,l,k.
Once we obtain the valuesf∗eh,sh,k, the sum of weighted distances from vertices of Gh to VGh,h,k can be calculated as(23)FGhVGh,h,k=f∗eh,sh,k.
We assignVGh,h,k=V∗eh,sh,k.
According to our assumption, we obtain(24)f∗Veh,0,1=∑graftBi∈sonhFGBi,hVGBi,h,h,1+∑cycleBj∈sonhFGBj,hVGBj,h,h,h,1,and assign(25)V∗eh,0,1=h.


### 3.3.1. The Calculation off∗Veh,l,k and V∗eh,l,k

Suppose that, when the phasej begins, the value FGBi,hVGBi,h,h,1 or FGBi,hVGBi,h,h,h,1 has been calculated for each block Bi∈TG of level levBi≥Lm−j+1. In the phase j, we search all hinges of level Lm−j. For each of these hinges h, we calculate all values f∗Veh,sh,k by the following method, and then, go to the next hinge with level Lm−j.Assuming that, for alll′<l, the values f∗Veh,l′,k have been calculated. Then, the value f∗Veh,l,k can be calculated as follows:(26)f∗Veh,l,k=min1≤k′≤k−1f∗Veh,l−1,k′+FGBl,hVGBl,h,h,k−k′,if Bl is graft, otherwise,(27)f∗Veh,l,k=min1≤k′≤k−1f∗Veh,l−1,k′+FGBl,hVGBl,h,h,h,k−k′.IfBl is graft, set(28)V∗eh,l,k=V∗eh,l−1,k′∪VGBl,h,h,k−k′,otherwise, set(29)V∗eh,l,k=V∗eh,l−1,k′∪VGBl,h,h,h,k−k′,where V∗eh,l−1,k′, VGBl,h,h,k−k′, and VGBl,h,h,h,k−k′ are the corresponding sets to f∗Veh,l−1,k′, FGBl,hVGBl,h,h,k−k′, and FGBl,hVGBl,h,h,h,k−k′, respectively.There are at mostVTGp values f∗Veh,l,k which can be calculated by traversing the edges in TG. Each calculation contains finding the minimum in at most 2k terms. Then, all the values f∗Veh,l,k can be computed in OVTGp2 time.Last,WGh is assigned as WGh=∑Bi∈sonhWGBi,h−whsh−1, which takes constant time.


## 3.3.1. The Calculation off∗Veh,l,k and V∗eh,l,k

Suppose that, when the phasej begins, the value FGBi,hVGBi,h,h,1 or FGBi,hVGBi,h,h,h,1 has been calculated for each block Bi∈TG of level levBi≥Lm−j+1. In the phase j, we search all hinges of level Lm−j. For each of these hinges h, we calculate all values f∗Veh,sh,k by the following method, and then, go to the next hinge with level Lm−j.Assuming that, for alll′<l, the values f∗Veh,l′,k have been calculated. Then, the value f∗Veh,l,k can be calculated as follows:(26)f∗Veh,l,k=min1≤k′≤k−1f∗Veh,l−1,k′+FGBl,hVGBl,h,h,k−k′,if Bl is graft, otherwise,(27)f∗Veh,l,k=min1≤k′≤k−1f∗Veh,l−1,k′+FGBl,hVGBl,h,h,h,k−k′.IfBl is graft, set(28)V∗eh,l,k=V∗eh,l−1,k′∪VGBl,h,h,k−k′,otherwise, set(29)V∗eh,l,k=V∗eh,l−1,k′∪VGBl,h,h,h,k−k′,where V∗eh,l−1,k′, VGBl,h,h,k−k′, and VGBl,h,h,h,k−k′ are the corresponding sets to f∗Veh,l−1,k′, FGBl,hVGBl,h,h,k−k′, and FGBl,hVGBl,h,h,h,k−k′, respectively.There are at mostVTGp values f∗Veh,l,k which can be calculated by traversing the edges in TG. Each calculation contains finding the minimum in at most 2k terms. Then, all the values f∗Veh,l,k can be computed in OVTGp2 time.Last,WGh is assigned as WGh=∑Bi∈sonhWGBi,h−whsh−1, which takes constant time.


## 3.4. The Procedure HINGEGhc,h

In this subsection, given a hingeh and the relevant subcactus Ghc, our task is to calculate the sum of weighted distances from vertices in Ghcs to h and the total weights of Ghc.


### 3.4.1. The Calculation ofFGhch and WGhc

We start by assigningWGB,h0c=0 and FGB,h0ch0=0. Suppose that, when the phase j begins, the value of FGhch and WGhc has been calculated for each hinge h∈TG with level levh<j. In the phase j, we search all hinges of level j. For each of these hinges h, set(30)WGhc=WGh0−WGh.Suppose thatfarh=B′ in TG and the hinge of B′ is h′ (Figure 3). Then, FGhch can be computed as follows:(31)FGhch=FGh′ch′+WGh′cdh′,h+FGB′,h′VGB′,h′,h,1−FGhVGh,h,1,if B′ is a graft, otherwise,(32)FGhch=FGh′ch′+WGh′cdh′,h+FGB′,h′VGB′,h′,h,h,1−FGhVGh,h,1.Note that all valuesFGhch and WGhc can be calculated by traversing all vertices of TG “downward.” The total calculations take OVTG time.


## 3.4.1. The Calculation ofFGhch and WGhc

We start by assigningWGB,h0c=0 and FGB,h0ch0=0. Suppose that, when the phase j begins, the value of FGhch and WGhc has been calculated for each hinge h∈TG with level levh<j. In the phase j, we search all hinges of level j. For each of these hinges h, set(30)WGhc=WGh0−WGh.Suppose thatfarh=B′ in TG and the hinge of B′ is h′ (Figure 3). Then, FGhch can be computed as follows:(31)FGhch=FGh′ch′+WGh′cdh′,h+FGB′,h′VGB′,h′,h,1−FGhVGh,h,1,if B′ is a graft, otherwise,(32)FGhch=FGh′ch′+WGh′cdh′,h+FGB′,h′VGB′,h′,h,h,1−FGhVGh,h,1.Note that all valuesFGhch and WGhc can be calculated by traversing all vertices of TG “downward.” The total calculations take OVTG time.


## 3.5. Algorithm for the CpM Problem

According to Lemma1, we can find a connected p median Vp∗ from V1∪V2∪V3. The sum of weighted distance from vertices of G to Xp∗ can be calculated as(33)FGVp∗=minminVGB,h,v,p∈V1FGB,hVGB,h,v,p+FGhch+WGhcdh,v,minVGB,h,vi,vj,p∈V2FGB,hVGB,h,vi,vj,p+FGhch+WGhcmindh,vi,dh,vj,minVGh,h,p∈V3FGhVGh,h,p+FGhch.Next, we design Algorithm1 to solve the CpM problem. For a given cactus graph G, as a preprocessing of Algorithm 1, first, the distance-matrix of the cactus will be calculated. Then, we construct the rooted skeleton graph of the cactus and calculate maximum level Lm. This preprocessing will be finished in On2 time.Algorithm 1: An algorithm for the connected p-median problem of cactus graphs.
Input: A cactus graph G, the corresponding rooted skeleton TG, and the maximum level LmOutput: A connected p median Vp∗ and the sum of weighted distance to Vp∗(1)
SetV1=V2=V3=∅(2)
fori=Lm;i≥0;i−do(3)
for vertex v∈TG with levv=ido(4)
ifv represents a graft Bthen(5)
Find the companion hinge ofB in TG, assuming it to h, and calculate the level L′(6)
CallGRAFTB,h to calculate the values FGB,hVGB,h,v,k and find VGB,h,v,k for v∈Bh of level j and all possible integers k, and set V1=V1+VGB,h,v,p.(7)
end(8)
ifv represent a cycle Bthen(9)
Find the companion hinge ofB in TG, assuming it to h(10)
CallCYCLEB,h to calculate the values FGB,hVGB,h,vi,vj,k and find VGB,h,vi,vj,k for vi,vj⊂VB of i≤j and all possible integers k, and set V2=V2+VGB,h,vi,vj,p.(11)
end(12)
ifv represents a hinge hthen(13)
CallHINGEGh,h to calculate the values FGhVGh,h,k and find VGh,h,k for all possible integers k, and set V3=V3+VGh,h,p.(14)
end(15)
end(16)
end(17)
fori=0;i≤Lm−1;i++do(18)
CallHINGEGhc,h to calculate the values FGhch and WGhc for each hinge h of levh=i(19)
end(20)
return use formula (33) to calculate FGVp∗ and find a connected p-median Xp∗.Since there are at mostOn2 elements in V1∪V2∪V3, the calculation of FGVp∗ takes On2 time. Then, we can use the following theorem to end this section.Theorem 1.
On the cactus graph withn vertices, the CpM problem can be solved in On2p2 time.


## 4. Concluding Remarks

In this article, we consider the connectedp-median problem on cactus graph and design an algorithm with time complexity On2p2 for it. In the following, it is meaningful to consider the connected p-median problems on other classes of graphs, such as planar graphs, interval graphs, and circular-arc graphs.



---

*Source: 3533623-2021-12-28.xml*