Algorithms for connected p-centdian problem on block graphs

Abstract

We consider the facility location problem of locating a set $X_p$ of p facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set $X_p$ is connected. Two problems on a block graph G are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of G to $X_p$, another problem is to minimize the maximum distance from each vertex that is not in $X_p$ to $X_p$ and, at the same time, to minimize the sum of its distances from all vertices of G to $X_p$. We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in $O(n^2)$ time, where n is the number of vertices of the block graph G.

1 Introduction

In network location theory, two main criteria that are often used on a network for locating a facility is: the maximal distance between the facility and a customer and the average distance between the facility and the customers. However, neither of the two criteria above alone capture all essential elements of a location problem. The sum of the distances criterion alone may result in solutions which are unacceptable from the point of view of the service level for the clients who are located far away from the facilities. On the other hand, the criterion of the minimization of the maximum distance, if used alone, may lead to very costly service systems. To capture more real-word problems and provide good ways to trade-off minisum and minimax approaches, Halpern (1976) introduce the centdian criteria which combine the minimax and minisum objective functions.

Problems of locating a facility at a point of a network with combinations of the two criteria are investigated and efficient algorithms for them are developed in Halpern (1978), Handler (1985) and Hansen et al. (1991). Averbakh and Berman (1999) considered problems of finding the optimal location of a path (of unrestricted length) on a tree, using different combinations of the minisum and minimax criteria. Becker et al. (2007) considered the first two problems introduced in Averbakh and Berman (1999) with an additional constraint, namely that the two optimal paths must have length (or cost) bounded by a fixed constant. Tamir et al. (2002) studied the problem finding the optimal location of a tree shaped facility of a specified size in a tree network by a convex combination of the minisum and minimax criteria and developed an $O(n\,logn)$ algorithm.

Yen (2012) studied the connected p-center problem on block graphs. Shan et al. considered the connected p-center and connected p-median problems on interval and circular-arc graphs and showed that all the problems can by solved in polynomial time. In this paper we consider problems of finding the optimal location of connected p-median and connected p-centdian (defined by bi-objective criterion) on a block graph.

The paper is organized as follows. In the next section we formally introduce the notation and the problems that we study in this paper. In Sect. 3, we study the connected p-median problem on block graphs, we prove that the connected p-median problem is linearly solvable on block graphs with unit edge length. Section 4 studies the connected p-centdian problem on unweighted block graphs. We give some properties of the Pareto-optimal solutions and prove that there are at most n Pareto-optimal solutions. Then two algorithms are proposed to obtain all the Pareto-optimal solutions. In the last section, we describe an example to illustrate the whole process to find all the Pareto-optimal solutions of the connected p-centdian problem on an unweighted block graphs.

2 Problem formulation

Let $G=(V,E,w,l)$ ba a finite, connected, undirected graph with vertex set V of order $n=|V|$ and edge set E of size $m=|E|$, where each vertex $v\in V$ is associated with a nonnegative weight w(v) and each edge $(v_i,v_j)\in E$ is associated with a certain cost or length $l(v_i,v_j)$. For convenience, we denote $G=(V,E)$ as the unweighted graph that $w(v)=1$ for all vertex $v\in V$ and $l(e)=1$ for all edge $e\in E$, and $G=(V,E,w)$ as the graph that $l(e)=1$ for all edge $e\in E$.

For any two vertices of $u,v\in G$, a path from u to v is vertex-edge alternative sequence: $u=x_1,e_1, x_2,e_2, \ldots , x_s, e_s, x_{s+1}=v$ such that the $x_i$ are all distinct and $e_i=x_ix_{i+1}$ for $i=1, 2, \ldots , s$. The number of edges of a path is its length. Let $d(u,v)=\sum _{i=1}^sl(e_i)$ be the length of a shortest path in G between u and v, called the distance of two vertices u and v. Let P(u, v) denotes a shortest path between u and v, and particularly L(P(u, v)) denotes the length of path P(u, v). Clearly, $d(u,v)=L(P(u,v))$. For any p-vertex set $X_p=\{x_{1},\ldots ,x_{p}\}$ of G, let $\langle X_p\rangle$ denote the subgraph induced by $X_p$ and $d(v,X_p)=\mathrm{min}_{1\le j\le p}\{d(v,x_i)\}$ denote the distance between vertex v and vertex set $X_p$. A p-vertex set $X_p$ is called a connected p-vertex set if $\langle X_p\rangle$ is a connected subgraph of G. Let $\varPhi$ be the collection of all connected p-vertex sets of the graph G.

Given a graph G, a vertex u is called a cut vertex of G if $\kappa (G-\{u\})>\kappa (G)$, where $\kappa (G)$ denotes the number of components of G. A connected subgraph H of G is called a block of G if H is maximal and it contains no cut vertices. A graph G is a block graph if all blocks of G are cliques and any two distinct blocks $B_1$ and $B_2$ have at most one common vertex (Behtoei et al. 2010), where a clique in a graph is a complete subgraph maximal under inclusion. In this paper we investigate the location problems on block graph. Throughout this paper, G denotes a block graph.

The minimax objective seeks a connected p-vertex set $X_p$ on the graph G that minimize the maximum weighted distances from each vertices to $X_p$:

$$\begin{aligned} \mathrm{min}_{X_p\in \varPhi }F_1(X_p), \, \, \text{ where }\,\, F_1(X_p)=\mathrm{max}_{v\in V}\left\{ w(v)d(v,X_p)\right\} . \end{aligned}$$

This problem is known as connected p-center (CpC) problem and studied in Yen (2012). Yen (2012) shown that the CpC problem is NP-hard on block graphs G when $w(v)=1$ for all vertices v and $l(e)=\{1,2\}$ for all edges e. We consider the following two problems on block graph G:

Problem 1

Find a connected p-vertex set $X_p$ on the graph G that minimize the sum of its distances from all vertices of G to $X_p$:

$$\begin{aligned} \mathrm{min}_{X_p\in \varPhi }F_2(X_p), \, \, \text{ where }\,\, F_2(X_p)=\sum _{v\in V}w(v)d(v,X_p). \end{aligned}$$

This problem is known as the connected p-median problem (CpM).

Problem 2

Find the set of all Pareto-optimal solutions $\varPi$ of the bi-objective problem:

$$\begin{aligned} \left\{ \mathop {{\mathrm{min}}}\limits _{X_p\in \varPhi }F_1(X_p),\mathop {{\mathrm{min}}}\limits _{X_p\in \varPhi }F_2(X_p)\right\} , \end{aligned}$$

where a connected p-vertex set $X_p\in \varPhi$ is called Pareto-optimal, if there is no connected p-vertex set $X'_p\in \varPhi$ such that $F_1(X'_p)\le F_1(X_p)$ and $F_2(X'_p)\le F_2(X_p)$ and at least one is satisfied as strict inequality. We call this problem the connected p-centdian problem.

Given a block graph $G=(V,E)$, let r be a vertex of G, we consider the rooted block graph G(r). Each vertex v of G(r) is associated with a label L(v), called the level of v which can be computed by the BFS traversal in O(n) time. The parent of v, denoted by par(v), is the vertex u such that $(v,u)\in E$ and $L(v)=L(u)+1$. Note that $par(v)=null$ if $v=r$. The children-set of v, denoted by chi(v), is defined as $chi(v)=\{w\,|\,(v,w)\in E~and~L(w)=L(v)+1\}$. The descendant-set of v, denoted by des(v), is defined as $des(v)=\{w\,|\,L(w)>L(v)~and~v\in P(w,r)\}$. If des(v) is empty, then v is called a leaf vertex of G(r). Otherwise, v is a non-leaf vertex of G(r). G(v) denotes the subgraph of G(r) induced by $\{v\}\cup des(v)$. We define $W(v)=\sum _{u\in G(v)}w(u)$ which can computed bottom-up by the following formula:

$$\begin{aligned} W(v)=w(v)+\mathop {\sum }\limits _{u\in chi(v)}W(u). \end{aligned}$$

(1)

When we consider unweighted block graph, W(v) is the number of vertices in subgraph G(v). For each vertex v of G(r), let $cs(v)=\{u\,|\,(u,v)\in E~and~L(u)=L(v)\}$. Note that cs(v) may be empty under this definition.

Consider the block graph $G=(V,E,w)$ and vertex $r\in V$. For a vertex v of the rooted block graph G(r), let f(v) and g(v) be the sum of the weighted distance from vertices of G(v) to v and vertices of $G(r)-G(v)$ to v, respectively. By assumption, $l(e)=1$ for each edge $e\in G$. Then

$$\begin{aligned} f(v)= & {} \mathop {\sum }\limits _{u\in G(v)}w(u)d(u,v) \nonumber \\= & {} \sum _{z\in chi(v)}f(z)+\sum _{z\in chi(v)}W(z) \nonumber \\= & {} \mathop {\sum }\limits _{u\in G(v)-v}W(u), \end{aligned}$$

(2)

and

$$\begin{aligned} g(v)= & {} \mathop {\sum }\limits _{u\in G(r)-G(v)}w(u)d(u,v) \nonumber \\= & {} \mathop {\sum }\limits _{u\in G(r)-G(par(v))}w(u)d(u,v)+\mathop {\sum }\limits _{u\in G(par(v))-G(v)}w(u)d(u,v) \nonumber \\= & {} g(par(v))+W(r)-W(par(v))+f(par(v))-(f(v)+W(v))\nonumber \\&+\left( W(par(v))-W(v)-\sum _{z\in cs(v)}W(z)\right) \nonumber \\= & {} g(par(v))+f(par(v))-f(v)+W(r)-2W(v)-\sum _{z\in cs(v)}W(z). \end{aligned}$$

(3)

Note that $g(r)=0$ and $F_2(v)=f(v)+g(v)$ for each vertex v of G.

3 The CpM problem on block graphs with unit edge length

In this section we consider the connected p-median (CpM) problem on a block graph $G=(V,E,w)$. We show that the CpM problem on G with unit edge length is linearly solvable.

Suppose that m is the 1-median of G and m belongs to a block $B_j=\{m=v_1, v_2,\ldots ,v_t\}$ of G. When we delete all the edges in $B_j$, we obtain a collection of connected components $G_1,\ldots ,G_t$ with $v_i\in G_i$, $1\le i\le t$. Let $W(G_i)=\sum _{v\in G_i}w(v)$. For each vertex $v\in G_i$, $d(v,m)=d(v,v_i)+d(v_i,m)$. Then, we have

$$\begin{aligned} F_2(m)= & {} \mathop {\sum }\limits _{v\in G}w(v)d(v,m) \nonumber \\= & {} \mathop {\sum }\limits ^{t}_{i=1}\mathop {\sum }\limits _{v\in G_i}w(v)d(v,v_i)+ \mathop {\sum }\limits ^{t}_{i=1}\left( \mathop {\sum }\limits _{v\in G_i}w(v)\right) d(v_i,m) \nonumber \\= & {} \mathop {\sum }\limits ^{t}_{i=1}\mathop {\sum }\limits _{v\in G_i}w(v)d(v,v_i)+ \mathop {\sum }\limits ^{t}_{i=1}W(G_i)-W(G_1). \end{aligned}$$

Because $v_1=m$ is the 1-median of G, $F_2(m)=\mathrm{min}_{1\le i\le t}\{F_2(v_i)\}$. Then, $W(G_1)=\mathrm{max}_{1\le i\le t}\{W(G_i)\}$. We have the following lemma.

Lemma 1

If the 1-median vertex m of G belongs to a block $B_j$, then m is the vertex of $B_j$ with maximum value $W(G_i)$.

Chen et al. (1985) obtained an extension version of Goldman’s algorithm which can find either the 1-median of G or the single block of G containing the 1-median of G in linear time. The following lemma is a direct consequence of their result.

Lemma 2

The 1-median of a block graph G can be found in linear time.

Lemma 3

If m is the 1-median of a block graph $G=(V,E,w)$, then there exist a connected p-median $X^*_p$ of G containing the vertex m.

Proof

By contradiction, suppose that $X^*_p$ is a connected p-median of G such that $d(m,X^*_p)$ is minimized and $m\notin X^*_p$. Assume that x is a vertex in $X^*_p$ such that $d(m,x)=d(m,X^*_p)$ and $x'$ is a vertex in path P(m, x) which is adjacent to vertex x. We may assume that the 1-median vertex m of G belongs to a block $B_j$ of G. Delete all the edges in $B_j$, we consider connected components of $G-E(B_j)$. Assume that $G_{m}$ is the component of $G-E(B_j)$ containing m. Since G is a block graph, there exists a vertex $y\in X_p$ such that $y\not =x$ and $\langle X_p-y\rangle$ is connected. Let

$$\begin{aligned} V_x= & {} \left\{ v\,|\, d(v,x)=d(v,X_p), v\in V\right\} \\ V_y= & {} \left\{ v\,|\, d(v,y)=d(v,X_p), v\in V-V_x\right\} . \end{aligned}$$

Set $X'_p=X^*_p-\{y\}+\{x'\}$. Obviously, $\langle X'_p\rangle$ is connected and $d(m,X'_p)<d(m,X^*_p)$. We obtain a contradiction by showing $F_2(X'_p)\le F_2(X^*_p)$.

Suppose that $X^*_p\subseteq G-G_m$. Then, we have

$$\begin{aligned} F_2\left( X'_p\right) -F_2\left( X^*_p\right) \le \mathop {\sum }\limits _{v\in V_{y}}w(v)-\mathop {\sum }\limits _{v\in G_m}w(v). \end{aligned}$$

Since m is a 1-median vertex of G, $V_y$ belongs to a component of $G-E(B_j)-G_m$. By Lemma 1, we have

$$\begin{aligned} \sum _{v\in V_{y}}w(v)\le \sum _{v\in G_m}w(v). \end{aligned}$$

Thus $F_2(X'_p)\le F_2(X^*_p)$. But $d(m,X'_p)<d(m,X^*_p)$. This contradicts the minimality of $d(m,X^*_p)$.

Suppose that $X^*_p\subseteq G_m$. Then, we have

$$\begin{aligned} F_2\left( X'_p\right) -F_2\left( X^*_p\right) \le \mathop {\sum }\limits _{v\in V_{y}}w(v)-\mathop {\sum }\limits _{v\in G-G_m+m}w(v). \end{aligned}$$

Since $X_p\subseteq G_m$, there exists another block $B_k\ne B_j$ such that $m\in B_k$ and y is contained in a component of $G-E(B_k)$. Denote by $G_y$ the component containing y. Since $\langle X_p\rangle$ is connected, in view of the choices of x and y, $V_y\subseteq V(G_y)$. By Lemma 1, we have

$$\begin{aligned} \sum _{v\in V_{y}}w(v)\le \sum _{v\in G_{y}}w(v)\le \sum _{v\in G-G_m+m}w(v). \end{aligned}$$

Thus $F_2(X'_p)\le F_2(X^*_p)$, contradicting the minimality of $d(m,X^*_p)$ again. $\square$

Lemma 4

Let m be the 1-median of a block graph $G=(V,E,w)$. For the rooted graph G(m), let $X^*_p=\{v_1,\ldots ,v_{p}\}$ be a p-vertex set of G such that $W(v_1),\ldots ,W(v_{p})$ are the first p largest numbers among $\{W(v)\,|\, v\in G(m)\}$ and $L(v_1),\ldots ,L(v_p)$ as small as possible. Then, $X^*_p$ is a connected p-median of G.

Proof

Obviously, for each non-root vertex v, $W(v)\le W(par(v))$. This implies that $m\in X^*_p$. Next we show that $X^*_p$ is connected. We will prove this statement by induction on p. Without loss of a generality, we may assume that $W(v_1)\ge W(v_2)\ge \cdots \ge W(v_n)$, and $X^*_i=\{v_1,\ldots ,v_{i}\}$, $1\le i\le p$.

It is trivial that $\langle X^*_1\rangle$ is connected. Assume that $\langle X^*_k\rangle$ is connected for $1\le k<p$. The choice of $v_{k+1}$ implies that $v_{k+1}\in \{y\,|\, y\in chi(X^*_k)-X^*_k\}$. Then $\langle X^*_{k+1}\rangle$ is connected.

It is easily seen that

$$\begin{aligned} F_2\left( X^*_p\right) = F_2\left( X^*_{p-1}\right) -W(x_p) = F_2(m)-\mathop {\sum }\limits _{v\in X^*_p-m}W(v). \end{aligned}$$

By Lemma 3 and the assumption of the lemma, for any connected p-vertex set $X'_p\ne X^*_p$ of G, we have

$$\begin{aligned} \sum _{v\in X^*_p}W(v)\ge \sum _{v\in X'_p}W(v). \end{aligned}$$

Thus $F_2(X^*_p)\le F_2(X'_p)$, so $X^*_p$ is an optimal solution. $\square$

By Lemma 2, the 1-median m can be found in O(n). Lemma 4 implies that we can construct $X^*_p$ in O(n) by considering the rooted graph G(m). Then we get the main result in this section.

Theorem 1

For a given block graph $G=(V,E,w)$ on n vertices, the CpM problem can be solved in O(n) time.

4 The connected p-centdian problem on unweighted block graphs

We now turn our attention to the connected p-centdian problem on unweighted block graphs. Given an unweighted block graph G(V, E), the notation $P(u^*,v^*)$ denotes a diameter path of G, i.e., $L(P(u^*,v^*))\ge L(P(u, v))$, for all $u, v\in V$. For a path P(u, v) of G, a middle vertex of P(u, v) is a vertex x in P(u, v) such that $d(u,x)=\lceil L(P(u,v))/2\rceil$ or $d(x,v)=\lceil L(P(u,v))/2\rceil$. In Yen (2012) Yen gave an algorithm to find a diameter path $P(u^*,v^*)$ in an unweighted block graph G in $O(n+m)$ time. Obviously, the 1-center vertex c is the middle vertex of diameter path $P(u^*,v^*)$ and $F_1(c)=\lceil L(P(u^*,v^*))/2\rceil$. Hence, we can find the 1-center vertex of an unweighted block graph in $O(n+m)$ time. As we have seen in Sect. 3, we can find the 1-median of G in linear time.

Lemma 5

Let c be the 1-center vertex and m the 1-median vertex in a block graph $G=(V,E)$. For any connected p-vertex set $X_p\in \varPi$, we have $X_p\cap P(c,m)\ne \emptyset$.

Proof

By contradiction, we suppose that $X_p\in \varPi$, $X_p\cap P(c,m)=\emptyset$ and $d(P(c,m),X_p)$ is minimized. Let x be a vertex in $X_p$ such that $d(P(c,m),x)=d(P(c,m),X_p)$. Assume that $x'$ is adjacent to x and $x'$ is a vertex on the shortest path from x to P(c, m). Since G is a block graph, there exists a vertex $y\in X_p$ such that $y\not =x$ and $\langle X_p-y\rangle$ is connected. Let

$$\begin{aligned} V_x= & {} \left\{ v\,|\, d(v,x)=d(v,X_p), v\in V\right\} ,\\ V_y= & {} \left\{ v\,|\, d(v,y)=d(v,X_p), v\in V-V_x\right\} . \end{aligned}$$

Set $X'_p=X_p-\{y\}+\{x'\}$. Obviously, $\langle X'_p\rangle$ is connected, $d(P(c,m),X'_p)=d(P(c,m),X_p)-1$ and $d(c,X'_p)=d(c,X_p)-1$.

Since c lies on the diameter path $P(u^*.v^*)$, c is a cut vertex. Let $G_{u^*}$ and $G_{v^*}$ be the subgraphs of $G-\{c\}$ containing $u^*$ and $v^*$, respectively. Since $c\notin X_p$ and $\langle X_p\rangle$ is connected, $X_p$ cannot lie within two distinct subgraphs $G_{u^*}$ and $G_{v^*}$. We have

$$\begin{aligned} F_1(X_p)= & {} \mathrm{max}\{d(u^*,X_p),d(v^*,X_p)\} \\= & {} \lceil L(P(u^*,v^*))/2\rceil +d(c,X_p)\ \text{ or }\ \lfloor L(P(u^*,v^*))/2\rfloor +d(c,X_p). \end{aligned}$$

Similarly, we have

$$\begin{aligned} F_1\left( X'_p\right) =\lceil L(P(u^*,v^*))/2\rceil +d\left( c,X'_p\right) \ \text{ or }\ \lfloor L(P(u^*,v^*))/2\rfloor +d\left( c,X'_p\right) . \end{aligned}$$

Obviously, $X_p$ and $X'_p$ lies in the same component of $G-\{c\}$. We have

$$\begin{aligned} F_1(X_p)-F_1\left( X'_p\right) =d(c,X_p)-d\left( c,X'_p\right) =1. \end{aligned}$$

Thus $F_1(X'_p)<F_1(X_p)$.

We assume that the 1-median vertex m of G belongs to a block $B_j$ of G. Deleting all the edges in $B_j$, we obtain a collection of connected components. Suppose $G_m$ is the component containing m. If $X_p\subseteq G-G_m$, then we have

$$\begin{aligned} F_2\left( X'_p\right) -F_2(X_p)\le \mathop {\sum }\limits _{v\in V_{y}}w(v)-\mathop {\sum }\limits _{v\in G_m}w(v). \end{aligned}$$

Since $\langle X_p\rangle$ is connected, in view of the choices of x and y, $V_y$ belongs to a component of $G-E(B_j)-G_m$. From Lemma 1, it immediately follows that

$$\begin{aligned} \sum _{v\in V_{y}}w(v)\le \sum _{v\in G_m}w(v). \end{aligned}$$

Thus $F_2(X'_p)\le F_2(X_p)$. If $X_p\subseteq G_m$, then we have

$$\begin{aligned} F_2\left( X'_p\right) -F_2(X_p)\le \mathop {\sum }\limits _{v\in V_{y}}w(v)-\mathop {\sum }\limits _{v\in G-G_m+m}w(v). \end{aligned}$$

Since $X_p\subseteq G_m$, there exists another block $B_k\ne B_j$ such that $m\in B_k$ and y is contained in a component of $G-E(B_k)$. Denote by $G_y$ the component containing y. Since $\langle X_p\rangle$ is connected, in view of the choices of x and y, $V_y\subseteq V(G_y)$. By Lemma 1, we have

$$\begin{aligned} \sum _{v\in V_{y}}w(v)\le \sum _{v\in G_{y}}w(v)\le \sum _{v\in G-G_m+m}w(v). \end{aligned}$$

Thus $F(X'_p)\le F(X_p)$. This contradicts the assumption that $X_p$ is Pareto-optimal. $\square$

Lemma 6

Let $X_p\in \varPi$, the 1-center vertex $c\notin X_p$ and x be a vertex of $X_p$ such that d(x, c) is minimum. For the rooted graph G(c), let $x_2,\ldots ,x_p$ be the vertices such that $W(x_2),\ldots ,W(x_p)$ are the first $p-1$ largest numbers among $\{W(v)\,|\, v\in G(x)\cup _{z\in cs(x)}G(z)-\{x\}\}$ and $L(x_2),\ldots ,L(x_p)$ as small as possible. Then $X_p=\{x,x_2,\ldots ,x_p\}$.

Proof

Using the similar reasoning in the proof of Lemma 4, we can deduce that $X_p\in \varPhi$. Since x is a vertex of $X_p$ and d(x, c) is minimum, $X_p$ contain only vertices in $G(x)\cup _{z\in cs(x)}G(z)$. Then we have

$$\begin{aligned} F_1(X_p)= & {} \mathrm{max}_{v\in V}\{d(v,X_p)\} \\= & {} \lceil L(P(u^*,v^*))/2\rceil +d(x,c)\ \text{ or }\ \lfloor L(P(u^*,v^*))/2\rfloor +d(x,c), \end{aligned}$$

and

$$\begin{aligned} F_2(X_p)= & {} \mathop {\sum }\limits _{v\in G(c)}d(v,X_p) \\= & {} \mathop {\sum }\limits _{v\in G(c)-G(x)}d(v,X_p)+\mathop {\sum }\limits _{v\in G(x)}d(v,X_p) \\= & {} g(x)-\sum _{x'\in X_p\cap (\cup _{z\in cs(x)}G(z))}W(x')+f(x)-\sum _{x'\in X_p\cap G(x)-\{x\}}W(x')\\= & {} F_2(x)-\mathop {\sum }\limits _{x'\in X_p-x}W(x'). \end{aligned}$$

Hence, for any $X'_p\in \varPhi$, where $x\in X'_p$ and $X'_p\subseteq G(x)\cup _{z\in cs(x)}G(z)$, we have

$$\begin{aligned} \sum _{v\in X_p}W(v)\ge \sum _{v\in X'_p}W(v). \end{aligned}$$

Thus $F_2(X_p)\le F_2(X'_p)$, and so $X_p$ is Pareto-optimal. $\square$

We choose 1-center vertex c as the root of G and compute W(v) for $v\in G(c)$ by (1). Find the optimal solution Q of G by the algorithm in Yen (2012) and set $\beta _1=F_1(Q)$. For each vertex v of G(c), define $\mu (v)=\mathrm{max}\{d(y,v)\,|\, y\in G(v)\}$. Then we have:

$$\begin{aligned} \mu (v)=\left\{ \begin{array}{ll} 0 &{} \quad \text{ if } chi(v)=\emptyset ,\ \ \ \\ \mathrm{max}\{\mu (u)\,|\, u\in chi(v)\}+1 &{} \quad \text{ if } chi(v)\ne \emptyset .\ \ \ \end{array} \right. \end{aligned}$$

(4)

For integer k with $\beta _1\le k\le F_1(c))$, let $Y_k=\{x\,|\, x\in G(c),\mu (v)\ge k\}$. Then $Y_k$ is the minimum set of connected vertices of G such that $F_1(Y_k)=k$ and $|Y_k|\le p$. It is easy to check that $Y_k$ can be found in O(n) time.

Let $X_p\in \varPi$ and $c\in X_p$. The definition of $Y_k$ implies that $Y_k\subseteq X_p$. The proof of the following lemma is similar to the proof of Lemma 6, and is omitted.

Lemma 7

Suppose $X_p\in \varPi$, $c\in X_p$ and $F_1(X_p)\le k$, where $\beta _1\le k\le F_1(c)$. Consider the rooted graph G(c). Then $X_p=Y_k\cup \{x_1,\ldots ,x_{p-|Y_k|}\}$, where $W(x_1),\ldots ,W(x_{p-|Y_k|})$ are the first $p-|Y_k|$ largest numbers among $\{W(v)\,|\, v\in G(c)-Y_k\}$ and $L(x_1),\ldots ,L(x_{p-|Y_k|})$ as small as possible.

According to Lemmas 5,  6 and  7, we now provide Algorithm 1 for finding a set $\varPsi$ containing all Pareto-optimal solutions.

Lemma 8

Algorithm 1 can obtain a set $\varPsi$ such that $\varPi \subseteq \varPsi \subseteq \varPhi$ and $|\varPi |\le n$ in $O(n^2)$ time.

Proof

Obviously, all $X^{y_i}_p$ and $X^k_p$ are connected p-vertex sets, i.e. $\varPsi \subseteq \varPhi$. By Lemma 5, for any connected p-vertex set $X_p\in \varPi$, we have $X_p\cap P(c,m)\ne \emptyset$. By Lemma 6, Steps 6–10 in Algorithm 1 find all $X_p\in \varPi$ with $c\notin X_p$. By Lemma 7, Steps 11–16 in Algorithm 1 find all $X_p\in \varPi$ with $c\in X_p$. Note that some $X_p\in \varPsi$ may not be Pareto-optimal. Thus $\varPi \subseteq \varPsi$. We have:

$$\begin{aligned} |\varPi |\le |\varPsi |\le L(P(m,c))+F_1(c)-\beta _1\le \frac{n}{2}+\frac{n}{2}=n. \end{aligned}$$

The 1-center vertex c can be found in $O(n+m)$ and the 1-median can be found in O(n). In Steps 3–5, the values $F_2(y_i)$ $(1\le i\le t)$ can be computed in O(n) time. The Steps 6–10 take $t-1$ times and each loop takes O(n) time. The Steps 11–16 take $F_1(c)-\beta _1$ times and each loop takes O(n) time. Thus, the total computational complexity is $O(n^2)$. $\square$

Based on Algorithm 1, we give Algorithm 2 to find all Pareto-optimal solutions.

Given $\varPsi$, Algorithm 2 can obtain the Pareto-optimal set $\varPi$ of the connected p-centdian problem in $O(n\,logn)$ time. Thus, we have:

Theorem 2

The Pareto-optimal set $\varPi$ of the connected p-centdian problem can be obtained in $O(n^2)$ time.

5 An example for the connected p-centdian problem

In this section we exhibit an example to illustrate how Algorithm 1 and 2 work. Let G be an unweighted block graph, which is shown in Fig. 1 and $p=5$.

Fig. 1

Illustration for the example

Table 1 W(v) for all $v\in G$

First, by applying Algorithm 1, we obtain:

• 1. The diameter path $P(u^*,v^*)$ and the middle vertex c, the 1-median m;

• 2. $F_1(c)=5$ and $P(m,c)=\{y_1,y_2,y_3\}$;

• 3. The connected 5-center $Q=\{y_1,y_2,y_3,v_{22},v_{19}\}$, and $\beta _1=F_1(Q)=3$;

• 4. W(v) for all $v\in G$ is presented in Table 1;

• 5. $F_2(y_1)=76$, $F_2(y_2)=79$, $F_2(y_3)=84$;

• 6. $X^{y_1}_{5}=\{y_1,v_{11},v_{12},v_{13},v_6\}$, $F_1(X^{y_1}_{5})=7$, $F_2(X^{y_1}_{5})=61$,

     $X^{y_2}_{5}=\{v_{11}, v_{12}, v_{13}, y_2,y_1 \}$, $F_1(X^{y_2}_{5})=6$, $F_2(X^{y_2}_{5})=52$;

• 7. $Y_5=\{y_3\}$, $X^5_{5}=\{y_3,y_2,y_1,v_{12},v_{22}\}$, $F_1(X^5_{5})=4$, $F_2(X^5_{5})=43$,

     $Y_4=\{y_3,y_2,v_{22}\}$, $X^4_{5}=\{y_3,y_2,y_1,v_{12},v_{22}\}$, $F_1(X^4_{5})=4$, $F_2(X^4_{5})=43$,

     $Y_3=\{y_3,y_2, y_1, v_{19},v_{22}\}=X^3_{5}$, $F_1(X^3_{5})=3$, $F_2(X^3_{5})=44$;

• 8. $\varPsi =\{X^{y_1}_5,X^{y_2}_5,X^4_5,X^3_5\}$.

Further, by applying Algorithm 2, we obtain:

• 1. $h_1(X^3_5)=1$, $h_1(X^4_5)=2$, $h_1(X^{y_2}_5)=3$, $h_1(X^{y_1}_5)=4$,

     $h_2(X^4_5)=1$, $h_2(X^3_5)=2$, $h_2(X^{y_2}_5)=3$, $h_2(X^{y_1}_5)=4$;

• 2. $\varPi =\{X^4_5,X^3_5\}$.