An Optimal Placement of a Liaison with Short Communication Lengths Between Two Members of the Same Level in an Organization Structure of a Complete K-ary Tree

Abstract

This paper proposes a model of placing a liaison which forms relations to two members in the same level of a pyramid organization structure when lengths between the liaison and the other members are less than those between members except the liaison in the organization such that the communication of information between every member in the organization becomes the most efficient. For a model of adding a node of liaison which gets adjacent to two nodes with the same depth in a complete $K$-ary tree of height $H$ where the lengths of edges between the liaison and the other members are $L(0<L<1)$ while those of edges between members except the liaison are $1$, an optimal pair of two nodes to which the node of liaison gets adjacent is obtained by maximizing the total shortening distance which is the sum of shortening lengths of shortest paths between every pair of all nodes in the complete $K$-ary tree.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The pyramid organization structure can be expressed as a rooted tree, if we let nodes and edges in the rooted tree correspond to members and relations between members in the organization respectively. Then the pyramid organization structure is characterized by the number of subordinates of each member, that is, the number of children of each node and the number of levels in the organization, that is, the height of the rooted tree [3, 7]. Moreover, the path between a pair of nodes in the rooted tree is equivalent to the route of communication of information between a pair of members in the organization, and adding edges to the rooted tree is equivalent to forming additional relations other than that between each superior and his direct subordinates [6].

Liaisons [2] which have roles of coordinating different sections are also placed as a means to become effective in communication of information in an organization. We have proposed some models of placing a liaison which forms relations to members in the same level of a pyramid organization structure which is a complete $K$-ary $(K=2,3,\ldots )$ tree of height $H(H=2,3,\ldots )$ [4, 5]. When a node of liaison which gets adjacent to nodes with the same depth is placed, an optimal depth is obtained by minimizing the sum of lengths of shortest paths between every pair of all nodes in the complete $K$-ary tree. These models are expressed as all edges have the same length. However, we should consider that edges between the liaison and the other members are shorter than those between members except the liaison in the organization.

This paper proposes a model of placing a liaison which forms relations to two members in the same level of a pyramid organization structure which is a complete $K$-ary tree of height $H$ when lengths between the liaison and the other members are less than those between members except the liaison in the organization. The lengths of edges between the liaison and the other members are $L(0<L<1)$ while those of edges between members except the liaison are $1$. This paper obtains an optimal pair of two members to which the liaison forms relations such that the communication of information between every member in the organization becomes the most efficient. This means to obtain an optimal pair of two nodes to which the node of liaison gets adjacent minimizing the sum of lengths of shortest paths between every pair of all nodes when an added node of liaison gets adjacent to two nodes with the same depth of a complete $K$-ary tree of height $H(H=1,2,\ldots )$. A complete $K$-ary tree is a rooted tree in which all leaves have the same depth and all internal nodes have $K$ children [1].

If $l_{i,j} (= l_{j,i})$ denotes the distance, which is length of the shortest path from a node $\textit{v}_i$ to a node $\textit{v}_j$ in the complete $K$-ary tree of height $H$, then $\sum _{i<j}l_{i,j}$ is the total distance. Furthermore, if $l^{\prime }_{i,j}$ denotes the distance from $v_i$ to $v_j$ after getting adjacent in the above model, $l_{i,j} - l^{\prime }_{i,j}$ is called the shortening distance between $v_i$ and $v_j$, and $\sum _{i<j}(l_{i,j} - l^{\prime }_{i,j})$ is called the total shortening distance. Minimizing the total distance is equivalent to maximizing the total shortening distance.

2 Formulation of Total Shortening Distance

This section formulates the total shortening distance when a node of liaison is added and gets adjacent to two nodes with the same depth $N(N=1,2,\ldots ,H)$ in a complete $K$-ary $(K=2,3,\ldots )$ tree of height $H(H=1,2,\ldots )$. The lengths of edges between the node of liaison and the two nodes to which the node of liaison gets adjacent are $L(0<L<1)$ while those of edges between nodes except the node of liaison are $1$. Since we don’t consider efficiency of communication of information between the liaison and the other members, the total shortening distance doesn’t include the shortening distance between the node of liaison and the other nodes in a complete $K$-ary tree.

The node of liaison can get adjacent to two nodes with the same depth $N$ of a complete $K$-ary tree in $N$ ways that lead to non-isomorphic graphs. Let $R_H(N,D)$ denote the total shortening distance by getting adjacent to two nodes, where $D(D=0,1,2,\ldots ,N-1)$ is the depth of the deepest common ancestor of the two nodes to which the node of liaison gets adjacent. For the case of $D=0$, the total shortening distance is denoted by $S_H(N)$. Since getting adjacent to two nodes shortens distances only between pairs of descendants of the deepest common ancestor of the two nodes to which the node of liaison gets adjacent, we obtain

$$\begin{aligned} R_H(N,D) = S_{H-D}(N-D) . \end{aligned}$$

(1)

We formulate $S_H(N)$ in the following. Let $v_0^X$ and $v_0^Y$ denote the two nodes to which the node of liaison gets adjacent and assume that $D=0$. Let $v_k^X$ and $v_k^Y$ denote ancestors of $v_0^X$ and $v_0^Y$, respectively, with depth $N-k$ for $k=1,2,\ldots ,N-1$. The sets of descendants of $v_0^X$ and $v_0^Y$ are denoted by $V_0^X$ and $V_0^Y$ respectively. (Note that every node is a descendant of itself [1].) Let $V_k^X$ denote the set obtained by removing the descendants of $v_{k-1}^X$ from the set of descendants of $v_k^X$ and let $V_k^Y$ denote the set obtained by removing the descendants of $v_{k-1}^Y$ from the set of descendants of $v_k^Y$, where $k=1,2,\ldots ,N-1$.

Since getting adjacent to two nodes doesn’t shorten distances between pairs of nodes other than between pairs of nodes in $V_k^X(k=0,1,2,\ldots ,N-1)$ and nodes in $V_k^Y(k=0,1,2,\ldots ,N-1)$, the total shortening distance can be formulated by adding up the following three sums of shortening distances:

• 1. The sum of shortening distances between every pair of nodes in $V_0^X$ and nodes in $V_0^Y$.

• 2. The sum of shortening distances between every pair of nodes in $V_0^X$ and nodes in $V_k^Y(k=1,2,\ldots ,N-1)$ and between every pair of nodes in $V_0^Y$ and nodes in $V_k^X(k=1,2,\ldots ,N-1)$.

• 3. The sum of shortening distances between every pair of nodes in $V_k^X(k=1,2,\ldots ,$ $N-1)$ and nodes in $V_k^Y(k=1,2,\ldots ,N-1)$.

The sum of shortening distances between every pair of nodes in $V_0^X$ and nodes in $V_0^Y$ is given by

$$\begin{aligned} A_H(N) = 2 \left\{ M(H-N) \right\} ^2 (N-L), \end{aligned}$$

(2)

where $M(h)$ denotes the number of nodes of a complete $K$-ary tree of height $h(h=0,1,2,\ldots )$. The sum of shortening distances between every pair of nodes in $V_0^X$ and nodes in $V_k^Y(k=1,2,\ldots ,N-1)$ and between every pair of nodes in $V_0^Y$ and nodes in $V_k^X(k=1,2,\ldots ,N-1)$ is given by

$$\begin{aligned} B_H(N) = 4 M(H-N) \sum _{i=1}^{N-1} \left\{ (K-1)M(H-i-1)+1 \right\} (i-L), \end{aligned}$$

(3)

and the sum of shortening distances between every pair of nodes in $V_k^X(k=1,2,\ldots ,N-1)$ and nodes in $V_k^Y(k=1,2,\ldots ,N-1)$ is given by

$$\begin{aligned} C_H(N)&= 2 \sum _{i=1}^{N-2} \left\{ (K-1)M(H-i-2)+1 \right\} \nonumber \\&\times \, \sum _{j=1}^{i} \left\{ (K-1)M(H-N+j-1)+1 \right\} (i-j-L+1), \end{aligned}$$

(4)

where we define $\sum \nolimits _{i=1}^{0}\cdot = 0$ and $\sum \nolimits _{i=1}^{-1}\cdot = 0$. From the above equations, the total shortening distance $S_H(N)$ is given by

$$\begin{aligned} S_H(N) = A_H(N) + B_H(N) + C_H(N) . \end{aligned}$$

(5)

3 An Optimal Depth $D^*$ for Each Depth $N$

This section shows an optimal depth $D^*$ of the deepest common ancestor of the two nodes which maximizes $R_H(N,D)$ for each depth $N$. From Eqs. (1) and (5) we have

$$\begin{aligned} R_H(N,D)&= 2 \left\{ M(H-N) \right\} ^2 (N-D-L) \nonumber \\&+ \, 4 M(H-N) \sum _{i=1}^{N-D-1} \left\{ (K-1)M(H-D-i-1)+1 \right\} (i-L) \nonumber \\&+ \, 2 \sum _{i=1}^{N-D-2} \left\{ (K-1)M(H-D-i-2)+1 \right\} \nonumber \\&\times \, \sum _{j=1}^{i} \left\{ (K-1)M(H-N+j-1)+1 \right\} (i-j-L+1) . \end{aligned}$$

(6)

Theorem 1

$D^*=0$ maximizes $R_H(N,D)$ for each $N$.

Proof

If $N=1$, then $D^*=0$ trivially. If $N \ge 2$, then $D^*=0$ since

$$\begin{aligned}&{R_H(N,D+1)-R_H(N,D)} \nonumber \\&\quad = - \, 2 \left\{ M(H-N) \right\} ^2 - 4 M(H-N) \left\{ (K-1)M(H-N)+1 \right\} (N-D-L-1) \nonumber \\&\qquad - \, 4 M(H-N) \sum _{i=1}^{N-D-2} (K-1) \left\{ M(H-D-i-1) - M(H-D-i-2) \right\} (i-L) \nonumber \\&\qquad - \, 2 \sum _{i=1}^{N-D-3} (K-1) \left\{ M(H-D-i-2) - M(H-D-i-3) \right\} \nonumber \\&\qquad \times \, \sum _{j=1}^{i} \left\{ (K-1)M(H-N+j-1) + 1 \right\} (i-j-L+1) \nonumber \\&\qquad - \, 2 \left\{ (K-1)M(H-N) + 1 \right\} \sum _{j=1}^{N-D-2} \left\{ (K-1)M(H-N+j-1)+1 \right\} \nonumber \\&\qquad \times \, (N-D-L-j-1) \nonumber \\&\quad < 0 \end{aligned}$$

(7)

for $D=0,1,2,\ldots ,N-2$. $\square$

Theorem 1 shows that the most efficient way of forming relations to two members in each level is that to two members which doesn’t have common superiors except the top.

Since the number of nodes of a complete $K$-ary tree of height $h$ is $M(h) = \left( K^{h+1} - 1\right) /\left( K-1\right)$, $S_H(N)$ of Eq. (5) becomes

$$\begin{aligned} S_H(N)&= \frac{1}{(K-1)^3} \bigl \{ (-2NL+2N)K^{2H-N+2} + (4NL-2N-2L)K^{2H-N+1} \nonumber \\&+ \, (-2NL+2L)K^{2H-N} + 4K^{H-N+1} + (4L-4)K^{H+1} - 4LK^H \nonumber \\&+ \, (2N-2L)K - 2N + 2L \bigr \} . \end{aligned}$$

(8)

4 An Optimal Depth $N^*$

This section seeks an optimal depth $N^*$ of two nodes which maximizes the total shortening distance $S_H(N)$ in Eq. (8).

Let $\Delta S_H(N) \equiv S_H(N+1) - S_H(N)$, so that we have

$$\begin{aligned} \Delta S_H(N)&= \frac{1}{(K-1)^2} \Bigl [ \bigl \{ (2NL-2N)K^2 + (-4NL+2N+2)K + 2NL \bigr \} K^{2H-N-1} \nonumber \\&- \, 4K^{H-N} + 2 \Bigr ] \end{aligned}$$

(9)

for $N = 1,2,\ldots ,H-1$.

Lemma 2

If $N \ge 2$, then $\Delta S_H(N) < 0$.

Proof

Let $Q_H(L) \equiv \Delta S_H(N)$. Since

$$\begin{aligned} \frac{dQ_H(L)}{dL} = 2NK^{2H-N-1} > 0 \end{aligned}$$

(10)

and

$$\begin{aligned} Q_H(1) = \frac{1}{(K-1)^2} \left[ \left\{ 2(K-1) \left( \frac{K}{K-1} - N \right) \right\} K^{2H-N-1} - 4K^{H-N} + 2 \right] < 0 \end{aligned}$$

(11)

for $N \ge 2$, we have $Q_H(L)<0$ for $N \ge 2$. ${}\square$

Let

$$\begin{aligned} \psi = 1 - \left( \frac{1-K^{-H+1}}{K-1} \right) ^2, \end{aligned}$$

(12)

so that we have Lemma 3.

Lemma 3

If $N=1$, then we have the following:

• (i) If $L < \psi$, then $\Delta S_H(N) < 0$.

• (ii) If $L = \psi$, then $\Delta S_H(N) = 0$.

• (iii) If $L > \psi$, then $\Delta S_H(N) > 0$.

Proof

(i) If $L < \psi$, then

$$\begin{aligned}&S_H(2) - S_H(1)=\frac{1}{(K-1)^2} \nonumber \\&\Bigl [ \bigl \{ (2L-2)K^2 + (-4L+4)K + 2L \bigr \} K^{2H-2} - 4K^{H-1} + 2 \Bigr ] < 0. \end{aligned}$$

(13)

(ii) If $L = \psi$, then $S_H(2) - S_H(1) = 0$.

(iii) If $L > \psi$, then $S_H(2) - S_H(1) > 0$. $\square$

From Lemma 2 and Lemma 3 we have the following theorem.

Theorem 4

(i) If $L < \psi$, then $N^*=1$.

(ii) If $L = \psi$, then $N^*=1, 2$.

(iii) If $L > \psi$, then $N^*=2$.