Linear-time algorithms for three domination-based separation problems in block graphs


The problems of determining minimum identifying, locating-dominating or open locating-dominating codes are special search problems that are challenging both from a theoretical and a computational point of view, even for several graph classes where other in general hard problems are easy to solve, like bipartite graphs or chordal graphs. Hence, a typical line of attack for these problems is to determine minimum codes of special graphs. In this work we study the problem of determining the cardinality of minimum such codes in block graphs (that are diamond-free chordal graphs). We present linear-time algorithms for these problems, as a generalization of a linear-time algorithm proposed by Auger in 2010 for identifying codes in trees. Thereby, we provide a subclass of chordal graphs for which all three problems can be solved in linear time. 

Introduction

For a graph G that models a facility or a multiprocessor network, detection devices can be placed at its vertices to locate an intruder (like a fire, a thief or a saboteur) or a faulty processor. Depending on the features of the detection devices (to detect an intruder only if it is present at the vertex v where the detector is installed and/or also at a vertex adjacent to v), different dominating sets can be used to determine the optimal distribution of the detection devices in G. In the following, we study three problems arising in this context which all have been actively studied during the last decade, see e.g. the bibliography maintained by Lobstein [16]. 
Let G = (V, E) be a graph. The (open) neighborhood of a vertex u is the set N (u) of all vertices of G adjacent to u, and N [u] = {u} ∪ N (u) is the closed neighborhood of u. 
Identifying codes A subset C ⊆ V is an identifying code (for short: 
ID- code) of G if • N [u] ∩ C = ∅ for all u ∈ V (domination), • N [u] ∩ C = N [v] ∩ C for all u, v ∈ V (separation),
see Figure 1(a) for an example. Identifying codes were introduced by Karpovsky et al. [15]. There it was noted that not every graph G admits an identifying code, i.e. is identifiable: this holds if and only if there are no true twins in G, i.e., there is no pair of distinct vertices u, v ∈ V with N [u] = N [v] [15]. On the other hand, for every identifiable graph, its whole vertex set trivially forms an identifying code. 
The identifying code number γ ID (G) of a graph G is the minimum cardinality of an identifying code of G. Determining γ ID (G) is in general NP-hard [10] and remains hard for several graph classes where other in general hard problems are easy to solve, including bipartite graphs [10] and two classes of chordal graphs, namely split graphs and interval graphs [12]. 
Hence, typical lines of attack for the identifying code problem are to determine minimum identifying codes of special graphs. Closed formulas for the exact value of γ ID (G) have been found so far only for restricted graph families (e.g. for paths and cycles [6], for stars [13], for complete multipartite graphs [1] and some subclasses of split graphs [3]). A linear-time algorithm to determine γ ID (G) if G is a tree was provided by Auger [5]. 
Locating-dominating codes A subset C ⊆ V is a locating-dominating code (for short: LD-code) of G if 
• N [u] ∩ C = ∅ for all u ∈ V , • N (u) ∩ C = N (v) ∩ C for all u, v ∈ V -C,
see Figure 1(b) for an example. Locating-dominating codes were introduced by Slater [20,21]. By definition, every graph has a locating-dominating code (as its whole vertex set trivially forms an LD-code). 
The locating-dominating number γ LD (G) of a graph G is the minimum cardinality of a locating-dominating code of G. Determining γ LD (G) is in general NP-hard [10] and even remains hard for bipartite graphs [10]. This result is extended to planar bipartite unit disk graphs in [17]. 
Hence, a typical line of attack for the LD-code problem is again to determine minimum LD-codes of special graphs. Closed formulas for the exact value of γ LD (G) have been found so far for restricted graph families as e.g. paths [21], cycles [6], stars, complete multipartite graphs and thin suns [4]. Bounds for the LD-number of trees were provided in [8], characterizations of trees with unique minimum locating-dominating sets were found in [7]. A linear-time algorithm to determine γ LD (G) if G is a tree was provided by Slater in [20]. 
Open locating-dominating codes A subset C ⊆ V is an open locatingdominating code (for short: OLD-code) of G if 
• N (u) ∩ C = ∅ for all u ∈ V (open-domination), • N (u) ∩ C = N (v) ∩ C for all u, v ∈ V (open-separation),
see Figure 1(c) for an example. Open locating-dominating codes were introduced by Seo and Slater [22]. There it was noted that not every graph G admits an OLD-code: this holds if and only if there are neither isolated vertices nor false twins in G (i.e., no pair of distinct vertices u, v ∈ V with N (u) = N (v)) [22]. On the other hand, the whole vertex set trivially forms an OLD-code of any false twin-free graph. 
The open locating-dominating number γ OLD (G) of a graph G is the minimum cardinality of an OLD-code of G. Determining γ OLD (G) is in general NP-hard [22] and remains NP-hard for perfect elimination bipartite graphs and APXcomplete for chordal graphs with maximum degree 4 [18]. Closed formulas for the exact value of γ OLD (G) have been found so far only for restricted graph families such as cliques and paths [22], some algorithmic aspects are discussed in [19]. More results on all three problems are listed in [16]. Concerning the relation of the three studied domination numbers, it is immediate from the definitions that γ LD (G) ≤ min{γ ID (G), γ OLD (G)} as every ID-code and every OLD-code satisfy the conditions for locatingdomination. 

(b) (c) (a)

In this paper, we determine the identifying code, locating-dominating and open locating-dominating numbers of block graphs. A block graph is a graph in which every maximal 2-connected subgraph (block) is a clique (see Figure 1). Block graphs are precisely the diamond-free chordal graphs [9] resp. those chordal graphs in which every two maximal cliques have at most one vertex in common [14]. 
We present linear-time algorithms for the three studied problems on block graphs, as a generalization of the linear-time algorithm by Auger [5] for γ ID (G) on trees. 
In fact, trees are exactly the block graphs with clique size 2 and constitute exactly the intersection of block graphs with bipartite graphs. 
Note that a tree is identifiable (i.e. has no true twins) whenever it is different from the clique of size 2, whereas a block graph B admits an identifying code if and only if each maximal clique K of B satisfies that all vertices in K, except at most one, have a neighbor that is not in V (K). 
In [22] it was observed that a tree has an OLD-code (i.e. has no false twins) if and only if no two vertices with degree one (called endpoints) have a common neighbor (called support vertex). It is straightforward to see that this condition carries over to block graphs. Also, a block graph B admits an OLD-code if and only if no vertex in G has more than one neighbor with degree one. 
Hence, in contrary to Auger's algorithm for identifying codes in trees, our algorithms have to take into account that the block graph given as input might not admit an ID-code or an OLD-code. 
In Section 2, we provide basic definitions and notations necessary for what follows. In Section 3, we present our general algorithmic framework for determining the three studied domination numbers in block graphs, and give the details and proofs for finding minimum ID-codes, LD-codes and OLD-codes in Sections 4, 5 and 6, resp. We close with some concluding remarks and lines of future research. The results on ID-codes were presented without proofs in [2]. 

Basic definitions and notations

In order to provide linear-time algorithms that compute γ ID (B), γ LD (B) and γ OLD (B) of a block graph B, we adopt the following notation from [5]. Let G = (V, E) be a graph and v ∈ V . Then C ⊆ V is a v-almost X-code of G where X ∈ {ID, LD, OLD}, if the code C is an X-code for the induced subgraph G -{v} of G. Moreover, we say that C satisfies the property 
• ID (LD, OLD) if C is an ID (LD or OLD resp.)-code in G, • CO if v ∈ C, • ADJ if v has a neighbour in C, • FN if v has a neighbour w with N [w] ∩ C = {v}, • OFN if v has a neighbour w with N (w) ∩ C = {v}, • P if C does not satisfy property P ∈ {ID, LD, OLD, CO, ADJ, F N, OF N }.
In properties F N and OF N the vertex w is called the favored neighbor of v. Let P = {ID, LD, OLD, CO, ADJ, F N, OF N, ID, LD, OLD, CO, ADJ, F N , OF N } and X ∈ {ID, LD, OLD}. We denote by γ P1,...,P k (v, G) the function that returns the minimum size of a v-almost X-code in G satisfying the properties {P 1 , . . . , P k } ⊂ P or ∞ if no such code exists. 
We observe that there exist dependency relationships between these properties. In fact, if a v-almost X-code C satisfies F N then it satisfies CO, if C satisfies ID or LD then it satisfies CO or ADJ, if C satisfies ID, CO and F N then it must satisfy ADJ and finally, if C satisfies OLD then it must satisfy ADJ. As a consequence we observe the following: Remark 1 There is no v-almost X-code in G that satisfies the following sets of properties: 
Let X ∈ {ID, LD, OLD}. If v ∈ V (G), we denote by γ X (v, G) the minimum size of a v-almost X code. From Remark 1 it follows that γ ID (v, G) = min γ ID,CO,ADJ,F N (v, G), γ ID,CO,ADJ,F N (v, G) γ ID,CO,ADJ (v, G), γ ID,CO,ADJ (v, G) (1) 
γ LD (v, G) = min{γ LD,CO (v, G), γ LD,CO (v, G)} (2) γ OLD (v, G) = min{γ OLD,CO,OF N (v, G), γ OLD,CO,OF N (v, G), γ OLD,CO (v, G)} (3 
) In the particular case of a block graph, we observe the following. If B is a block graph, v 1 ∈ V (B) and K a maximal clique with V (K) = {v 1 , . . . , v k } then deleting all the edges in K yields k block subgraphs, say B 1 , B 2 , . . . , B k , containing v 1 , v 2 , . . . , v k , respectively. In the sequel, it is therefore convenient to use the following notation: Notation 2 Let B be a block graph, v 1 a chosen vertex and K a maximal clique with vertices v 1 , . . . , v k , i.e., containing v 1 . We denote by B 1 , . . . , B k the block graphs, containing v 1 , . . . , v k respectively, obtained from B after deletion of the edges in K. 
Remark 3 Let X ∈ {ID, LD, OLD}, B be a block graph, V (K) = {v 1 , . . . , v k }. If C is a v 1 -almost X-code in B then C i = C ∩ V (B i ) is a v i -almost X-code in B i for all i ∈ {1, 2, . . . , k}. Lemma 4 Let X ∈ {ID, LD, OLD}, B be a block graph, V (K) = {v 1 , . . . , v k }. If C i is a v i -almost X-code in B i for i ∈ {1, 2, . . . , k}, and C = k i=1 C i then the vertices in V ′ = k i=1 (V (B i ) -{v i }) are dominated and separated by C. Proof. Observe that u, v are trivially separated if d(u, v) > 2. Consider u, v ∈ V ′ such that d(u, v) ≤ 2. Hence u, v ∈ V (B i ) -{v i } for some i ∈ {1, 2, . . . , k}. By assumption C i is a v i -almost X-code in B i
for all i ∈ {1, 2, . . . , k}, the vertices in V ′ are dominated and separated by C. 
Lemma 5 Let X ∈ {ID, LD, OLD}, B be a block graph, V (K) = {v 1 , . . . , v k }. If C is a v 1 -almost X-code in B and C i = C ∩ V (B i ) ∀ i ∈ {1, 2 
, . . . , k} then, (i) if X = ID and C satisfies ID then there exists at most one i ∈ {1, 2, . . . , k} such that C i satisfies ADJ, (ii) if X = LD (resp. OLD) and C satisfies LD (resp. OLD) then there exists at most one i ∈ {1, 2, . . . , k} such that C i satisfies ADJ and CO, (iii) if X = ID then there exists at most one i ∈ {2, . . . , k} such that C i satisfies ADJ, (iv) if X = LD (resp. OLD) then there exists at most one i ∈ {2, . . . , k} such that C i satisfies ADJ and CO. 
Proof. Consider the maximal clique K with 
V (K) = {v 1 , v 2 , . . . , v k }. If there is j ∈ {2 . . . , k} such that C 1 and C j satisfy ADJ then N [v j ] ∩ C = N [v 1 ] ∩ C = V (K) ∩ C.
Then C clearly does not satisfy ID, and (i) is proved. If in addition the same pair satisfies CO then 
N (v j ) ∩ C = N (v 1 ) ∩ C = V (K) ∩ C
and C is neither an LD-nor an OLD-code, proving (ii). Suppose that C is a v j -almost X-code with X ∈ {ID, LD, OLD}, then using the previous items the lemma follows. 
3 An algorithm for determining the minimum X-code of block graphs 
Let B be a block graph and v ∈ V (B), in order to obtain the X-number of B, with X ∈ {ID, LD, OLD}, we will prove that we need to compute 46 functions that are based on the formulas (1), ( 2) and (3). The first 27 functions will be called main functions and are given in Table 1 and the latter 21 auxiliary functions in Table 2. Sometimes it is necessary to point out the particular problem we are dealing with. In such cases, we write γ (P1,...,P k ) X (v, G) when properties P 1 , . . . , P k must be satisfied for the problem X, with X ∈ {ID, LD, OLD}. 
Observe that if B = {v} the values of the functions are straightforward and are also given in Table 1 and2. 
Name Function Initial value f j (v, {v}) f γ ID,CO,ADJ,F N ∞ f γ ID,CO,ADJ,F N ∞ f γ ID,CO,ADJ 1 f γ ID,CO,ADJ ∞ f γ (CO,ADJ,F N ) ID ∞ f γ (CO,ADJ,F N ) ID ∞ f γ (CO,ADJ,F N ) ID ∞ f γ (CO,ADJ,F N ) ID 1 f γ (CO,ADJ) ID ∞ f 10 γ (CO,ADJ) ID 0 f 11 γ LD,CO 1 f 12 γ LD,CO ∞ f 13 γ (CO,ADJ,F N ) LD ∞ f 14 γ (CO,ADJ,F N ) LD ∞ f 15 γ (CO,ADJ,F N ) LD ∞ f 16 γ (CO,ADJ,F N ) LD 1 f 17 γ (CO,ADJ) LD ∞ f 18 γ (CO,ADJ) LD 0 f 19 γ OLD,CO,OF N ∞ f 20 γ OLD,CO,OF N ∞ f 21 γ OLD,CO ∞ f 22 γ CO,ADJ,OF N ∞ f 23 γ CO,ADJ,OF N ∞ f 24 γ CO,ADJ,OF N ∞ f 25 γ CO,ADJ,OF N 1 f 26 γ (CO,ADJ) OLD ∞ f 27 γ (CO,ADJ) OLD 0
Table 1: List of main functions together with their initial values f j (v, {v}). 
According to the notation introduced in Table 1, we can rewrite the formulas (1), ( 2) and (3). 
γ ID (v, B) = min {f 1 (v, B), f 2 (v, B), f 3 (v, B), f 4 (v, B)} γ LD (v, B) = min {f 11 (v, B), f 12 (v, B)} γ OLD (v, B) = min {f 19 (v, B), f 20 (v, B), f 21 (v, B)} (4)
Below, we present the algorithms XB for X ∈ {ID, LD, OLD} that find γ X (v, B) applying the equations above. 

Name Function

Initial value f j (v, {v}) 
f 28 γ (CO,ADJ) ID = min{f 7 , f 8 } 1 f 29 γ (CO,ADJ) ID = min{f 5 , f 6 } ∞ f 30 γ (CO,F N ) ID = min{f 5 , f 7 } ∞ f 31 γ (CO,F N ) ID = min{f 6 , f 8 } 1 f 32 γ CO ID = min{f 9 , f 10 } 0 f 33 γ ADJ ID = min{f 5 , f 6 , f 9 } ∞ f 34 γ ID,CO,ADJ = min{f 1 , f 2 } ∞ f 35 γ (CO∨ADJ) LD = min{f 13 , f 14 , f 15 , f 16 , f 17 } 1 f 36 γ (CO,F N ) LD = min{f 14 , f 16 } 1 f 37 γ (CO,F N ) LD = min{f 13 , f 15 } ∞ f 38 γ CO LD = min{f 17 , f 18 } 0 f 39 γ CO LD = min{f 13 , f 14 , f 15 , f 16 } 1 f 40 γ OLD,CO = min{f 19 , f 20 } ∞ f 41 γ (CO,ADJ) OLD = min{f 22 , f 23 } ∞ f 42 γ (CO,ADJ) OLD = min{f 24 , f 25 } 1 f 43 γ CO OLD = min{f 22 , f 23 , f 24 , f 25 } 1 f 44 γ ADJ OLD = min{f 22 , f 23 , f 26 } ∞ f 45 γ (CO∨ADJ) OLD = min{f 22 , f 23 , f 24 , f 25 , f 26 } 1 f 46 γ CO,OF N = min{f 22 , f 24 } ∞ f 47 γ CO,OF N = min{f 23 , f 25 } 1 f 48 γ CO OLD = min{f 26 , f 27 } 0
Table 2: List of auxiliary functions together with their initial values f j (v, {v}). 
Algorithm 6 (Algorithm XB) Input: a connected block graph B and its list of maximal cliques. 
Output: γ X (B). 1: randomly select a vertex v 1 and call RXB(v 1 , B); 
2(If X = ID): return γ ID (v 1 , B) = min{f 1 (v 1 , B), f 2 (v 1 , B), f 3 (v 1 , B), f 4 (v 1 , B)}. 2(If X = LD): return γ LD (v 1 , B) = min{f 11 (v 1 , B), f 12 (v 1 , B)}. 2(If X = OLD): return γ OLD (v 1 , B) = min{f 19 (v 1 , B), f 20 (v 1 , B), f 21 (v 1 , B)}.
Algorithm RXB chooses a maximal clique K with vertices {v 1 , . . . , v k } and either returns the initial function values if K = {v 1 } or deletes all edges of K and calls recursively RXB(v i , B i ) for all so-obtained components B i of B -E(K) to compute the lists of functions LX i for (v i , B i ) with i ∈ {1, . . . , k} according to the problem X ∈ {ID, LD, OLD}. 
In the following sections, we use this common algorithmic scheme for all 3 studied problems and specify which of the main and auxiliary functions are relevant for the particular problem and how we can compute them in all 3 cases. 

Algorithm 7 (Algorithm RXB)

Input: a block graph B, its list of maximal cliques and v 1 ∈ V (B). 
Output: list L of the values of the main functions f j on (v 1 , B) corresponding to problem X. C i and 
V ′ = k i=1 (V (B i ) -{v i }).
(1) Let v ∈ V ′ and v j ∈ V (K) such that d(v, v j ) = 1. Then v j and v are dominated and separated by C if there is i ∈ {1, 2, . . . , k} i = j such that 
C i is CO. (2) Let v ∈ V ′ and v j ∈ V (K) with d(v, v j ) = 2.
Then v j and v are dominated and separated by C if C j satisfies CO or there is i ∈ {1, 2, . . . , k} i = j such that 
C i is CO and v / ∈ V (B i ). (3) Let v i , v j ∈ V (K) with i = j. Then v i and v j are dominated and separated by C if either C i or C j is ADJ. Proof. If v ∈ V ′ and v j ∈ V (K) such that d(v, v j ) = 1 then it is clear that v ∈ V (B j ). If there is i = j such that C i is CO then v i ∈ N [v j ] -N [v] and (1) follows. Let v ∈ V (B r ) -{v r } for some r ∈ {1, 2, . . . , k} and j ∈ {1, 2, . . . , k} such that d(v j , v) = 2. Clearly v j ∈ N [v r ] -N [v]. If v j ∈ C then (2) follows. Otherwise suppose that there is i = j such that v i ∈ C and i = r. Hence v i ∈ N [v j ] -N [v]
and this completes the proof of (2). 

It is easy to observe

that if C i (C j ) is ADJ then there is w ∈ (N [v i ] -N [v j ]) (w ∈ N [v j ] -N [v i ]) with w ∈ V (B i ) ∩ C i (w ∈ V (B j ) ∩ C j )
and the proof is complete. 
The following result shows how to compute f 1 (v 1 , B) for a given v 1 ∈ V (B). 
Theorem
∈ V (B 1 ). Since C is F N there is only one w ∈ V (B) -C such that N [w] ∩ C = {v 1 }.
We analyze the different cases that may occur (see Figure 2). If w = v j for some j ∈ {2, . . . , k} then C 1 is F N , C i is CO for all i = 1 and C j is ADJ. Then by Lemma 5 and the fact that 
C is ID it follows that C i is ADJ for all i = j. Since N (v 1 ) ∩ C ∩ V (B i ) = ∅ for all i = 1 and C is ID, C 1 is ID and (i) is proved. Now, if w ∈ V (B 1 ) then C 1 is F N . Since C is ADJ there is v ∈ N (v 1 ) ∩ C. If V (K) ∩ C = {v 1 } then v ∈ V (B 1 ) and C 1 is ADJ, C i is CO for all i = 1. Since C is ID and C 1 is F N it follows that C i is ADJ for all i = 1 and C 1 is ID. Then (v) follows. If |V (K) ∩ C| ≥ 2 then there is h = 1 such that C h is CO. Hence, if C i is ADJ for all i = 1 then we obtain (iv). But, if C h is ADJ, Lemma 5 implies that C i is ADJ for all i = h which proves (ii). In addition if there is j = h such that C j is ADJ and CO again from Lemma 5 C i is ADJ for all i = j which gives us (iii).
Conversely, let C i be a v i -almost identifying code in B i for all i ∈ {1, . . . , k} satisfying one of the sets of properties from (i) to (v) and let C = k i=1 C i (see Figure 2). We will prove that C is a v 1 -almost identifying code in B with the properties ID, CO, ADJ and F N . 
It is easy to see that C is CO and ADJ since C 1 is CO and either C 1 satisfies ADJ or C h is CO with h = 1 in each one of the statements (i) to (v). Also, it is easy to verify that each of the statements implies that C is F N . 
Then it remains to prove that C is ID, i.e., we need to prove that given u, v ∈ V (B) with d(u, v) ≤ 2 they are dominated and separated by C. When, r = 1 and i = 1, statements (ii) to (iv) say that there is h = 1 with v h ∈ C and Lemma 8 (2) ensures that v r and v are separated and dominated by 
From Lemma 4 if u, v ∈ k i=1 (V (B i ) -{v i }) the theorem follows. Consider u, v ∈ V (B) with d(u, v) = 2 such that u ∈ V (K). Then v ∈ V (B i ) -{v i }
C. If statement (i) holds then C 1 is F N and then there is w ∈ N [v] ∩ C ∩ V (B 1 ) and w / ∈ N [v r ]. If statement (v) is satisfied then C r is ADJ.
In both cases v and v r are dominated and separated by C. 
If u, v ∈ V (B) with d(u, v) = 1 such that u ∈ V (K) and v / ∈ V (K) then v ∈ V (B i ) -{v i } and u = v i
for some i. If i = 1 we see that statements (ii) to (iv) ensure there is h = 1 such that C h is CO while statements (i) and (v) state that C 1 is ID. Hence Lemma 8 (1) implies that they are dominated and separated. In case i = 1 all statements imply that C 1 is CO and the same lemma proves that u and v are dominated and separated by C. 
Finally, if u = v i and v = v j with i = j then either C i is ADJ or C j is ADJ but not both. Hence Lemma 8 (3) completes the proof.
In all the pictures used as illustrations for the proofs, black dots represent vertices in the corresponding code, white dots depict vertices out of the code and crosses represent vertices that may be or may not be in the code. From Theorem 9 we obtain the following: 
Corollary 10 With the notation of Theorem 9, we have the following equalities: 
• if k = 2, f1(v1, B) = min 8 > > > < > > > : f2(v1, B1) + f10(v2, B2) f5(v1, B1) + f28(v2, B2) f30(v1, B1) + f29(v2, B2) f1(v1, B1) + f9(v2, B2) • if k ≥ 3, then f1(v1, B) equals min 8 > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > : f2(v1, B1) + min j=2,...,k 8 < : f10(vj, Bj) + k P i=2 i =j f9(vi, Bi) 9 = ; f5(v1, B1) + min h=2,...,k 8 < : f28(v h , B h ) + k P i=2 i =j f33(vi, Bi) 9 = ; f5(v1, B1) + min j,h=2,...,k j =h 8 < : f10(vj, Bj) + f29(v h , B h ) + k P i=2 i =j,h f33(vi, Bi) 9 = ; f30(v1, B1) + min h=2,...,k 8 < : f29(v h , B h ) + k P i=2 i =h f33(vi, Bi) 9 = ; f1(v1, B1) + k P i=2 f9(vi, Bi)
In a similar way, the remaining main functions f j (v 1 , B) for j ∈ {2, . . . , 10} can be obtained. We give them in Tables 3,4, 5 and 6. 
Function Function 
f 1 (v 1 , B) = min 8 > > > < > > > : f 2 (v 1 , B 1 ) + f 10 (v 2 , B 2 ) f 5 (v 1 , B 1 ) + f 28 (v 2 , B 2 ) f 30 (v 1 , B 1 ) + f 29 (v 2 , B 2 ) f 1 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) f 6 (v 1 , B) = min 8 > < > : f 31 (v 1 , B 1 ) + f 28 (v 2 , B 2 ) f 31 (v 1 , B 1 ) + f 29 (v 2 , B 2 ) f 6 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) f 2 (v 1 , B) = min 8 > < > : f 6 (v 1 , B 1 ) + f 28 (v 2 , B 2 ) f 31 (v 1 , B 1 ) + f 29 (v 2 , B 2 ) f 2 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) f 7 (v 1 , B) = min ( f 7 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) f 8 (v 1 , B 1 ) + f 10 (v 2 , B 2 ) f 3 (v 1 , B) = f 3 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) f 8 (v 1 , B) = f 8 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) f 4 (v 1 , B) = min 8 > > > < > > > : f 9 (v 1 , B 1 ) + f 3 (v 2 , B 2 ) f 10 (v 1 , B 1 ) + f 2 (v 2 , B 2 ) f 9 (v 1 , B 1 ) + f 34 (v 2 , B 2 ) f 4 (v 1 , B 1 ) + f 4 (v 2 , B 2 ) f 9 (v 1 , B) = min 8 > < > : f 32 (v 1 , B 1 ) + f 3 (v 2 , B 2 ) f 32 (v 1 , B 1 ) + f 34 (v 2 , B 2 ) f 9 (v 1 , B 1 ) + f 4 (v 2 , B 2 ) f 5 (v 1 , B) = min 8 > > > < > > > : f 6 (v 1 , B 1 ) + f 10 (v 2 , B 2 ) f 30 (v 1 , B 1 ) + f 28 (v 2 , B 2 ) f 30 (v 1 , B 1 ) + f 29 (v 2 , B 2 ) f 5 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) f 10 (v 1 , B) = f 10 (v 1 , B 1 ) + f 4 (v 2 , B 2 ) Table 3: Case |V (K)| = 2 for RIDB.
From the formulas in Tables 3,4, 5 and 6, it is immediate to see that for each of the ten functions f j with j ∈ {1, . . . , 10}, we can compute 
f j (v 1 , B) from LID i (v i , B i ) for all i ∈ {1, . . . , k} in time O(k),
where k is the order of a maximal clique containing vertex v. 

Theorem 11 Algorithm IDB computes in linear time γ ID (B) of an identifiable block graph B or returns ∞ if no identifying code exists in B.

Proof. In what follows we call g(B) the number of operations the algorithm needs to solve the problem on graph B. The proof is by induction on the number of vertices of graph B. If V (B) = {v} then using the initial values we get that g(B) ∈ O(1). Assume that for every block graph with less than n vertices the result holds and let B be a block graph of order n. 
Let v ∈ V (B) and consider a maximal clique K containing v. Then, we erase all the edges in K and obtain 
|V (K)| = k block subgraphs called B i with i = 1, . . . , k. From induction hypothesis g(B i ) ∈ O(n i + m i ) where n i = |V (B i )| and m i = |E(B i )| for i = 1, . . . , k.
Then, in order to obtain γ ID (B) we need f j (v, B) for j ∈ {1, . . . , 10}. As we have mentioned above, this can be computed in time O(k). Then g(B) ∈ O(n + m) and the proof is complete. 

A linear-time algorithm for determining the locating-dominating number of B

We will see that the algorithm RLDB needs to compute the main functions f j (v 1 , B) with j ∈ {11, . . . , 18}. In fact, for i ∈ {1, . . . , k} we need the list LLD i that consists in functions f j (v i , B i ) for j ∈ {11, . . . , 18}, and in order to do so we need also the auxiliary functions f j (v i , B i ) for j ∈ {35, . . . , 39}. 
Theorem 12 Consider a block graph B and (i) C 1 is CO, F N , there exists j = 1 such that C j is CO and ADJ, and C i is CO and ADJ for all i = 1, j. 
V (K) = {v 1 , v 2 , . . . , v k }. Let C be a code in B and C i = C ∩ V (B i ) for all i ∈ {1, 2, . . . , k}. C is a v 1 -
(ii) If k ≥ 3, C 1 is CO, there exists h = 1 such that C h is CO, there exists j = 1, h such that C j is CO and ADJ, and C i is CO or ADJ for all i = j, h. 
(iii) C 1 is CO, and C i is CO or ADJ for all i. 
Proof. Let C be a v 1 -almost LD-code satisfying LD and CO. 
From Remark 3, C i is a v i -almost LD-code in B i for all i ∈ {1, . . . , k}. Also C 1 is CO, since C is CO and v 1 ∈ V (B 1
). In addition, Lemma 5 ensures that there is at most one j = 1 such that C j is CO and ADJ. 
Let j ∈ = 1 such that C j is CO and ADJ. Then, let u, v ∈ V (B), d(u, v) = 2 and u ∈ V (K). We have that v ∈ V (B i )-{v i } for some i and u = v r for r = i such that C r is CO. 
If C i is CO for all i = 1, C i is ADJ for all i = 1 and as C is LD, C 1 is F N and (i) holds. Now, let h = 1, j such that C h is CO. Then for all i = 1, j, h, C i is CO or ADJ and (ii) holds. Finally, if C i is CO or ADJ for all i = 1 then (iii) holds. Conversely, let C i be a v i -almost LD-code in B i for all i satisfying one of the statements from (i) to (iii) and let C = k i=1 C i . We will prove that C is a v 1 -almost LD-code in B with properties LD and CO. It is easy to see that C is CO since C 1 is CO in every case. Then to prove that C is LD we need to verify that u, v ∈ V (B), d(u, v) ≤ 2
If i = 1, u and v are dominated and separated by C since C 1 is CO. 
Let i = 1. In case (i), as C 1 is F N it exists w ∈ N [v] ∩ C -N (u), w = v 1 .
In the remaining cases, since C r is CO and it is ADJ or there exists h = 1 such that C h is CO. Then u and v are separated and dominated. 
Now, let u, v ∈ V (B), d(u, v) = 1, u ∈ V (K) and v / ∈ V (K). If u = v i for some i, then v ∈ V (B i ) -{v i } and C i is CO. Since i = 1
and C 1 is CO, u and v are separated and dominated. 
Finally, let u = v i and v = v j , i, j = 1 and C i , C j be CO. In all the cases, from Lemma 5 at least one of C i and C j is ADJ. Then u and v are separated and dominated. 
Corollary 13 With the notation of Theorem 12, we have: 
• for k = 2, f11(v1, B) = min ( f36(v1, B1) + f18(v2, B2) f39(v1, B1) + f35(v2, B2) • for k ≥ 3, f11(v1, B) equals min 8 > > > > > > > > > > > > < > > > > > > > > > > > > : f 36 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 18 (v j , B j ) + k P i=2 i =j f 17 (v i , B i ) 9 > = > ; f 39 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 18 (v j , B j ) + f 39 (v h , B h ) + k P i=2 i =j,h f 35 (v i , B i ) 9 > = > ; f 39 (v 1 , B 1 ) + k P i=2 f 35 (v i , B i )
In a similar way, the remaining main functions f j (v 1 , B) for j ∈ {12, . . . , 18} can be obtained. We give them in Tables 7,8, 9 and 10. 
From the formulas given in Tables 7, 8, 9 and 10, it is immediate to see that for each of the eight functions f j j ∈ 11, . . . , 18, we can compute 
f j (v 1 , B) from LLD i (v i , B i ) for all i ∈ {1, . . . , k} in time O(k).
The next result can be proved in a similar way as Theorem 11 was proved. 
Theorem 14 Algorithm LDB computes in linear time the locating-dominating number γ LD (B) of a block graph B. 

A linear-time algorithm for the open locatingdominating number of B

We will see that the algorithm ROLDB needs to compute the main functions f j (v 1 , B) with j ∈ {19, . . . , 27}, and in order to do so we need for all i ∈ {1, . . . , k} the main functions f j (v i , B i ) for j ∈ {19, . . . , 27} and the auxiliary functions f j (v i , B i ) for j ∈ {40, . . . , 48}. 
Theorem 15 Consider a block graph B and 
V (K) = {v 1 , v 2 , . . . , v k }. Let C be a code in B and C i = C ∩ V (B i ) for all i ∈ {1, 2, . . . , k}. C is a v 1 -
i = 1, h. (x) If k ≥ 3, C 1 is CO and OFN, there exist h, l = 1, h = l such that C h , C l are CO, and C i is CO or ADJ for all i = 1, h, l.
Proof. Let C be a v 1 -almost OLD-code satisfying OLD, CO and OF N . From Remark 3, 
C i is a v i -almost OLD-code in B i for all i. Also, C 1 is CO, since C is CO and v 1 ∈ V (B 1
). In addition, as C is OF N , there exists a unique 
w ∈ V (B) such that N (w) ∩ C = {v 1 }. Assume that w = v j for some j = 1, then C 1 is OF N , C i is CO for all i = 1, j and C j is ADJ. In addition, if C j is CO, then C i is ADJ for i = 1, j. Since N (v 1 ) ∩ C ∩ V (B i ) = ∅ for all i = 1
and C is OLD, we have that C 1 is OLD, and (i) holds. On one hand, if C j is CO, from Lemma 5 there exists at most one h = 1, j such that C h is ADJ. On the other hand, since C is OLD the neighbors of v j are open-separated from v 1 . Then, either C 1 is ADJ and (ii) is proved, or C j is OF N and (iii) holds. Now, if w ∈ V (B 1 ) then C 1 is OF N . We have to analyze different cases. 
Assume first that there exists j = 1 such that C j is CO and ADJ (such a j is unique from Lemma 5). As C 1 is OF N , there exists h = 1, j such that C h is CO. 
If C i is CO for all i = 1, h, C i is ADJ for all i = 1, j, h since C is OLD v j is open-separated from v i . Besides, as C 1 is OF N , we have that C h is ADJ and as C is OLD, v 1 is
open-separated from the vertices in N (v h ). Hence, either C 1 is ADJ and (iv) holds, or C h is OF N and (v) holds. 
Assume now that there exists at least two h, l = 1, j, h = l such that C h and C l are CO. Then C i is CO or ADJ for all i = 1, j, h, l, proving (vi). Now, if C i is CO or ADJ for all i = 1, we have three cases. 
If C i is CO for all i = 1, then C i is ADJ for all i = 1 and as C is OLD and N (v 1 ) ∩ C ∩ V (B i ) = ∅ for all i = 1, we have that C 1 is OLD proving (vii). If there exists a unique h = 1 such that C h is CO, then C i is CO and ADJ for all i = 1, h. In addition, as C 1 is OF N , we have that C h is ADJ. Now, as C is OLD, v 1 and the vertices in N (v h ) are open-separated, hence either C 1 is ADJ and (viii) holds, or C h is OF N and (ix) holds. 
Finally, if C h and C l are CO for some h, l = 1, h = l, C i is CO or ADJ for all i = 1, h, l and (x) holds. 
Conversely, let C i be a v i -almost OLD-code in B i for all i and let C = k i=1 C i . 
We will prove that C is a v i -almost OLD-code in B with properties OLD, CO and OF N . C is CO since C 1 is CO in all the sets of statements from (i) to (x). Also, it is immediate to check that C is OF N . 
To prove that C is OLD we need to verify that if In (v) and (ix) 
u, v ∈ V (B), d(u, v) ≤ 2 
(iii), if i = j, as C j is OF N there exists w = v j such that w ∈ (N (v) ∩ C) -N (u), otherwise, if i = j, v j ∈ (N (u) ∩ C) -N (u),
, if i = h as C h is OF N there exists w = v h such that w ∈ (N (v) ∩ C) -N (u), otherwise, if i = h, v h ∈ (N (u) ∩ C) -N (v),
, v ∈ V (B), d(u, v) = 1, u ∈ V (K) and v / ∈ V (K). Then, v ∈ V (B i ) -{v i } for some i and u = v i . If i = 1, in (i)
• if k = 2, then f19(v1, B) = min 8 > > > < > > > : f20(v1, B1) + f27(v2, B2) f19(v1, B1) + f26(v2, B2) f22(v1, B1) + f41(v2, B2) f46(v1, B1) + f23(v2, B2) • if k = 3, then f19(v1, B) equals min 8 > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > : f20(v1, B1) + min{f27(v2, B2) + f26(v3, B3), f26(v2, B2) + f27(v3, B3)} f23(v1, B1) + min{f48(v2, B2) + f42(v3, B3), f42(v2, B2) + f48(v3, B3)} f47(v1, B1) + min{f48(v2, B2) + f25(v3, B3), f25(v2, B2) + f48(v3, B3)} f22(v1, B1) + min{f27(v2, B2) + f41(v3, B3), f41(v2, B2) + f27(v3, B3)} f46(v1, B1) + min{f27(v2, B2) + f23(v3, B3), f23(v2, B2) + f27(v3, B3)} f19(v1, B1) + f26(v2, B2) + f26(v3, B3) f22(v1, B1) + min{f41(v2, B2) + f26(v3, B3), f26(v2, B2) + f41(v3, B3)} f46(v1, B1) + min{f23(v2, B2) + f26(v3, B3), f26(v2, B2) + f23(v3, B3)} f46(v1, B1) + f43(v2, B2) + f43(v3, B3) • if k ≥ 4, then f19(v1, B) equals min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 20 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 27 (v j , B j ) + k P i=2 i =j f 26 (v i , B i ) 9 > = > ; f 23 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 48 (v h , B h ) + f 42 (v j , B j ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 47 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 48 (v h , B h ) + f 25 (v j , B j ) + k P i=2 i =j f 26 (v i , B i ) 9 > = > ; f 22 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v j , B j ) + f 41 (v h , B h ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v j , B j ) + f 23 (v h , B h ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min j,h,l=2,...,k j =h,j =l,h =l 8 > < > : f 27 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + k P i=2 i =j,h,l f 45 (v i , B i ) 9 > = > ; f 19 (v 1 , B 1 ) + k P i=2 f 26 (v i , B i ) f 22 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 41 (v h , B h ) + k P i=2 i =h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 23 (v h , B h ) + k P i=2 i =h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min h,l=2,...,k h =l 8 > < > : f 43 (v h , B h ) + f 43 (v l , B l ) + k P i=2 i =h,l f 45 (v i , B i ) 9 > = > ;
In a similar way, the remaining main functions f j (v 1 , B) for j ∈ {20, . . . , 27} can be obtained, see Tables 11,12,13,14,15,16 and 17. From these formulas, it is immediate to see that for each of the nine functions f j j ∈ {19, . . . , 27}, we can compute f j (v 1 , B) from LOLD i (v i , B i ) for all i ∈ {1, . . . , k} in time O(k). 
The next result can be proved in a similar way as Theorem 11 was proved. 

Theorem 17 Algorithm OLDB computes in linear time γ OLD (B) of a block graph B (or returns ∞ if no open locating-dominating code exists in B).


Concluding remarks

The three here studied domination problems are challenging both from a theoretical and a computational point of view and even remain hard for several graph classes where other in general hard problems are easy to solve, including bipartite graphs and chordal graphs. 
In this paper, we present linear-time algorithms that find the identifying code, locating-dominating and open locating-dominating numbers of a given block graph, as a generalization of the linear-time algorithm proposed by Auger [5] for identifying codes in trees. Although our algorithms work in a similar way, they take into account the identifiable and open locating-dominating condition for block graphs and the recomposition steps are built by defining distinct functions accordingly. 
Thus, we provide a subclass of chordal graphs for which all the three here studied domination problems can be solved in linear time. Moreover, recall that trees are exactly the block graphs with clique size 2 and constitute exactly the intersection of block graphs with bipartite graphs. Hence, our results provide in particular a linear-time algorithm that finds the OLD-code number of a tree. 
Furthermore, note that our algorithms could be modified in order to obtain the studied code of minimum size, just by keeping track of the functions where the minimum values are attained. In addition, if B is a vertex-weighted block graph, the algorithms can be easily modified in order to return the minimum weighted identifying code number by just replacing in Table 1 and 2 the entry with value 1 by the weight corresponding to the vertex. 
Finally, it is interesting whether similar ideas could be adapted for graph classes with a similar structure, e.g. for cacti (graphs in which every maximal 2-connected subgraph is an edge or a cycle) or for block-cacti (graphs in which every maximal 2-connected subgraph is a clique or a cycle). 
Function 
f 1 (v 1 , B) = min 8 > > > > > < > > > > > : f 2 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 9 (v 3 , B 3 ), f 9 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 5 (v 1 , B 1 ) + min {f 28 (v 2 , B 2 ) + f 33 (v 3 , B 3 ), f 33 (v 2 , B 2 ) + f 28 (v 3 , B 3 )} f 5 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 29 (v 3 , B 3 ), f 29 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 30 (v 1 , B 1 ) + min {f 29 (v 2 , B 2 ) + f 33 (v 3 , B 3 ), f 33 (v 2 , B 2 ) + f 29 (v 3 , B 3 )} f 1 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) + f 9 (v 3 , B 3 ) f 2 (v 1 , B) = min 8 > > > < > > > : f 6 (v 1 , B 1 ) + min {f 28 (v 2 , B 2 ) + f 33 (v 3 , B 3 ), f 33 (v 2 , B 2 ) + f 28 (v 3 , B 3 )} f 6 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 29 (v 3 , B 3 ), f 29 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 31 (v 1 , B 1 ) + min {f 29 (v 2 , B 2 ) + f 33 (v 3 , B 3 ), f 33 (v 2 , B 2 ) + f 29 (v 3 , B 3 )} f 2 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) + f 9 (v 3 , B 3 ) f 3 (v 1 , B) = f 3 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) + f 9 (v 3 , B 3 ) f 4 (v 1 , B) = min 8 > > > > > > > > > > < > > > > > > > > > > : f 9 (v 1 , B 1 ) + min {f 28 (v 2 , B 2 ) + f 29 (v 3 , B 3 ), f 29 (v 2 , B 2 ) + f 28 (v 3 , B 3 )} f 9 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 2 (v 3 , B 3 ), f 2 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 9 (v 1 , B 1 ) + min {f 3 (v 2 , B 2 ) + f 9 (v 3 , B 3 ), f 9 (v 2 , B 2 ) + f 3 (v 3 , B 3 )} f 32 (v 1 , B 1 ) + f 29 (v 2 , B 2 ) + f 29 (v 3 , B 3 ) f 10 (v 1 , B 1 ) + min {f 2 (v 2 , B 2 ) + f 9 (v 3 , B 3 ), f 9 (v 2 , B 2 ) + f 2 (v 3 , B 3 )} f 9 (v 1 , B 1 ) + min {f 34 (v 2 , B 2 ) + f 9 (v 3 , B 3 ), f 9 (v 2 , B 2 ) + f 34 (v 3 , B 3 )} f 4 (v 1 , B 1 ) + f 4 (v 2 , B 2 ) + f 4 (v 3 , B 3 ) f 5 (v 1 , B) = min 8 > > > > > < > > > > > : f 6 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 9 (v 3 , B 3 ), f 9 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 30 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 29 (v 3 , B 3 ), f 29 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 30 (v 1 , B 1 ) + min {f 28 (v 2 , B 2 ) + f 33 (v 3 , B 3 ), f 33 (v 2 , B 2 ) + f 28 (v 3 , B 3 )} f 30 (v 1 , B 1 ) + min {f 29 (v 2 , B 2 ) + f 33 (v 3 , B 3 ), f 33 (v 2 , B 2 ) + f 29 (v 3 , B 3 )} f 5 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) + f 9 (v 3 , B 3 ) f 6 (v 1 , B) = min 8 > > > < > > > : f 31 (v 1 , B 1 ) + min {f 28 (v 2 , B 2 ) + f 33 (v 3 , B 3 ), f 33 (v 2 , B 2 ) + f 28 (v 3 , B 3 )} f 31 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 29 (v 3 , B 3 ), f 29 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 31 (v 1 , B 1 ) + min {f 29 (v 2 , B 2 ) + f 33 (v 3 , B 3 ), f 33 (v 2 , B 2 ) + f 29 (v 3 , B 3 )} f 6 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) + f 9 (v 3 , B 3 ) f 7 (v 1 , B) = min ( f 7 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) + f 9 (v 3 , B 3 ) f 8 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 9 (v 3 , B 3 ), f 9 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 8 (v 1 , B) = f 8 (v 1 , B 1 ) + f 9 (v 2 , B 2 ) + f 9 (v 3 , B 3 ) f 9 (v 1 , B) = min 8 > > > > > > > > < > > > > > > > > : f 32 (v 1 , B 1 ) + min {f 3 (v 2 , B 2 ) + f 9 (v 3 , B 3 ), f 9 (v 2 , B 2 ) + f 3 (v 3 , B 3 )} f 32 (v 1 , B 1 ) + min {f 10 (v 2 , B 2 ) + f 2 (v 3 , B 3 ), f 2 (v 2 , B 2 ) + f 10 (v 3 , B 3 )} f 32 (v 1 , B 1 ) + min {f 28 (v 2 , B 2 ) + f 29 (v 3 , B 3 ), f 29 (v 2 , B 2 ) + f 28 (v 3 , B 3 )} f 32 (v 1 , B 1 ) + f 29 (v 2 , B 2 ) + f 29 (v 3 , B 3 ) f 32 (v 1 , B 1 ) + min {f 34 (v 2 , B 2 ) + f 9 (v 3 , B 3 ), f 9 (v 2 , B 2 ) + f 34 (v 3 , B 3 )} f 9 (v 1 , B 1 ) + f 4 (v 2 , B 2 ) + +f 4 (v 3 , B 3 ) f 10 (v 1 , B) = f 10 (v 1 , B 1 ) + f 4 (v 2 , B 2 ) + f 4 (v 3 , B 3 ) Table 4: Case |V (K)| = 3 for RIDB. Function f 1 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > : f 2 (v 1 , B 1 ) + min j=2,...,k ( f 10 (v j , B j ) + P i=2,...,k,i =j f 9 (v i , B i ) ) f 5 (v 1 , B 1 ) + min h=2,...,k ( f 28 (v h , B h ) + P i=2,...,k,i =j f 33 (v i , B i ) ) f 5 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 10 (v j , B j ) + f 29 (v h , B h ) + k P i=2 i =j,h f 33 (v i , B i ) 9 > = > ; f 30 (v 1 , B 1 ) + min h=2,...,k ( f 29 (v h , B h ) + P i=2,...,k,i =h f 33 (v i , B i ) ) f 1 (v 1 , B 1 ) + k P i=2 f 9 (v i , B i ) f 2 (v 1 , B) = min 8 > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > : f 6 (v 1 , B 1 ) + min h=2,...,k ( f 28 (v h , B h ) + P i=2,...,k,i =h f 33 (v i , B i ) ) f 6 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 10 (v j , B j ) + f 29 (v h , B h ) + k P i=2 i =j,h f 33 (v i , B i ) 9 > = > ; f 31 (v 1 , B 1 ) + min h=2,...,k ( f 29 (v h , B h ) + P i=2,...,k,i =h f 33 (v i , B i ) ) f 2 (v 1 , B 1 ) + k P i=2 f 9 (v i , B i ) f 3 (v 1 , B) = f 3 (v 1 , B 1 ) + k P i=2 f 9 (v i , B i ) f 4 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 9 (v 1 , B 1 ) + min j,h,l=2,...,k j =h,j =l,h =l 8 > < > : f 10 (v j , B j ) + f 29 (v h , B h ) + f 29 (v l , B l ) + k P i=2 i =j,h,l f 33 (v i , B i ) 9 > = > ; f 9 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 28 (v j , B j ) + f 29 (v h , B h ) + k P i=2 i =j,h f 33 (v i , B i ) 9 > = > ; f 9 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 10 (v j , B j ) + f 2 (v h , B h ) + k P i=2 i =j,h f 9 (v i , B i ) 9 > = > ; f 9 (v 1 , B 1 ) + min h=2,...,k ( f 3 (v h , B h ) + P i=2,...,k,i =h f 9 (v i , B i ) ) f 32 (v 1 , B 1 ) + min h,l=2,...,k,h =l ( f 29 (v h , B h ) + f 29 (v l , B l ) + P i=2,...,k,i =h,l f 33 (v i , B i ) ) f 10 (v 1 , B 1 ) + min h=2,...,k ( f 2 (v h , B h ) + P i=2,...,k,i =h f 9 (v i , B i ) ) f 9 (v 1 , B 1 ) + min h=2,...,k ( f 34 (v h , B h ) + P i=2,...,k,i =h f 9 (v i , B i ) ) k P i=1 f 4 (v i , B i ) f 5 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > : f 6 (v 1 , B 1 ) + min j=2,...,k ( f 10 (v j , B j ) + P i=2,...,k,i =j f 9 (v i , B i ) ) f 30 (v 1 , B 1 ) + min j,h=2,...,k,j =h ( f 10 (v j , B j ) + f 29 (v h , B h ) + P i=2,...,k,i =j,h f 33 (v i , B i ) ) f 30 (v 1 , B 1 ) + min h=2,...,k ( f 28 (v h , B h ) + P i=2,...,k,i =h f 33 (v i , B i ) ) f 30 (v 1 , B 1 ) + min h=2,...,k ( f 29 (v h , B h ) + P i=2,...,k,i =h f 33 (v i , B i ) ) f 5 (v 1 , B 1 ) + k P i=2 f 9 (v i , B i ) Table 5: Case |V (K)| ≥ 4 for RIDB. 20 Function f 6 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > : f 31 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 29 (v h , B h ) + k P i=2 i =h f 33 (v i , B i ) 9 > = > ; f 31 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 10 (v j , B j ) + f 29 (v h , B h ) + k P i=2 i =j,h f 33 (v i , B i ) 9 > = > ; f 31 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 29 (v h , B h ) + k P i=2 i =h f 34 (v i , B i ) 9 > = > ; f 6 (v 1 , B 1 ) + k P i=2 f 9 (v i , B i ) f 7 (v 1 , B) = min 8 > > > > > < > > > > > : f 7 (v 1 , B 1 ) + k P i=2 f 9 (v i , B i ) f 8 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 10 (v j , B j ) + k P i=2 i =j f 9 (v i , B i ) 9 > = > ; f 8 (v 1 , B) = f 8 (v 1 , B 1 ) + k P i=2 f 9 (v i , B i ) f 9 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 32 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 3 (v h , B h ) + k P i=2 i =h f 9 (v i , B i ) 9 > = > ; f 32 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 10 (v j , B j ) + f 2 (v h , B h ) + k P i=2 i =j,h f 9 (v i , B i ) 9 > = > ;
f 32 (v 1 , B 1 ) + min j,h,l=2,...,k j =h,j =l,h =l 8 > < > : 
f 10 (v j , B j ) + f 29 (v h , B h ) + f 29 (v l , B l ) + k P i=2 i =j,h,l f 33 (v i , B i ) 9 > = > ; f 32 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 28 (v j , B j ) + f 28 (v h , B h ) + k P i=2 i =j,h f 33 (v i , B i ) 9 > = > ; f 32 (v 1 , B 1 ) + min h,l=2,...,k h =l 8 > < > : f 29 (v h , B h ) + f 29 (v l , B l ) + k P i=2 i =h,l f 33 (v i , B i ) 9 > = > ; f 32 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 34 (v h , B h ) + k P i=2 i =h f 9 (v i , B i ) 9 > = > ; f 9 (v 1 , B 1 ) + k P i=2 f 4 (v i , B i ) f 10 (v 1 , B)f = f 10 (v 1 , B 1 ) + k P i=2 f 4 (v i , B i ) Table 6: Case |V (K)| ≥ 4 for RIDB. Function Function f 11 (v 1 , B) = min ( f 36 (v 1 , B 1 ) + f 18 (v 2 , B 2 ) f 39 (v 1 , B 1 ) + f 35 (v 2 , B 2 ) f 15 (v 1 , B) = min ( f 16 (v 1 , B 1 ) + f 18 (v 2 , B 2 ) f 15 (v 1 , B 1 ) + f 17 (v 2 , B 2 ) f 12 (v 1 , B) = min 8 > < > : f 18 (v 1 , B 1 ) + f 36 (v 2 , B 2 ) f 12 (v 1 , B 1 ) + f 12 (v 2 , B 2 ) f 17 (v 1 , B 1 ) + f 39 (v 2 , B 2 ) f 16 (v 1 , B) = f 16 (v 1 , B 1 ) + f 17 (v 2 , B 2 ) f 13 (v 1 , B) = min 8 > < > : f 14 (v 1 , B 1 ) + f 18 (v 2 , B 2 ) f 13 (v 1 , B 1 ) + f 17 (v 2 , B 2 ) f 37 (v 1 , B 1 ) + f 39 (v 2 , B 2 ) f 17 (v 1 , B) = min ( f 17 (v 1 , B 1 ) + f 12 (v 2 , B 2 ) f 38 (v 1 , B 1 ) + f 39 (v 2 , B 2 ) f 14 (v 1 , B) = min ( f 14 (v 1 , B 1 ) + f 17 (v 2 , B 2 ) f 36 (v 1 , B 1 ) + f 38 (v 2 , B 2 ) f 18 (v 1 , B) = f 18 (v 1 , B 1 ) + f 12 (v 2 , B 2 ) Table 7: Case |V (K)| = 2 for RLDB. Function f 11 (v 1 , B) = min 8 > < > : f 36 (v 1 , B 1 ) + min {f 18 (v 2 , B 2 ) + f 17 (v 3 , B 3 ), f 17 (v 2 , B 2 ) + f (v 3 , B 3 )} f 39 (v 1 , B 1 ) + min {f 18 (v 2 , B 2 ) + f 39 (v 3 , B 3 ), f 39 (v 2 , B 2 ) + f (v 3 , B 3 )} f 39 (v 1 , B 1 ) + f 35 (v 2 , B 2 ) + f 35 (v 3 , B 3 ) f 12 (v 1 , B) = min 8 > > > > > < > > > > > : f 17 (v 1 , B 1 ) + min {f 18 (v 2 , B 2 ) + f 36 (v 3 , B 3 ), f 36 (v 2 , B 2 ) + f (v 3 , B 3 )} f 18 (v 1 , B 1 ) + min {f 36 (v 2 , B 2 ) + f 17 (v 3 , B 3 ), f 17 (v 2 , B 2 ) + f (v 3 , B 3 )} f 18 (v 1 , B 1 ) + f 39 (v 2 , B 2 ) + f 39 (v 3 , B 3 ) f 12 (v 1 , B 1 ) + f 12 (v 2 , B 2 ) + f 12 (v 3 , B 3 ) f 17 (v 1 , B 1 ) + min {f 39 (v 2 , B 2 ) + f 35 (v 3 , B 3 ), f 35 (v 2 , B 2 ) + f (v 3 , B 3 )} f 13 (v 1 , B) = min 8 > > > < > > > : f 14 (v 1 , B 1 ) + min {f 18 (v 2 , B 2 ) + f 17 (v 3 , B 3 ), f 17 (v 2 , B 2 ) + f (v 3 , B 3 )} f 13 (v 1 , B 1 ) + f 17 (v 2 , B 2 ) + f 17 (v 3 , B 3 ) f 37 (v 1 , B 1 ) + min {f 18 (v 2 , B 2 ) + f 39 (v 3 , B 3 ), f 39 (v 2 , B 2 ) + f (v 3 , B 3 )} f 37 (v 1 , B 1 ) + min {f 39 (v 2 , B 2 ) + f 35 (v 3 , B 3 ), f 35 (v 2 , B 2 ) + f (v 3 , B 3 )} f 14 (v 1 , B) = min 8 > < > : f 36 (v 1 , B 1 ) + min {f 18 (v 2 , B 2 ) + f 39 (v 3 , B 3 ), f 39 (v 2 , B 2 ) + f (v 3 , B 3 )} f 14 (v 1 , B 1 ) + f 17 (v 2 , B 2 ) + f 17 (v 3 , B 3 ) f 36 (v 1 , B 1 ) + min {f 39 (v 2 , B 2 ) + f 35 (v 3 , B 3 ), f 35 (v 2 , B 2 ) + f (v 3 , B 3 )} f 15 (v 1 , B) = min ( f 16 (v 1 , B 1 ) + min {f 18 (v 2 , B 2 ) + f 17 (v 3 , B 3 ), f 17 (v 2 , B 2 ) + f (v 3 , B 3 )} f 15 (v 1 , B 1 ) + f 17 (v 2 , B 2 ) + f 17 (v 3 , B 3 ) f 16 (v 1 , B) = f 16 (v 1 , B 1 ) + f 17 (v 2 , B 2 ) + f 17 (v 3 , B 3 ) f 17 (v 1 , B) = min 8 > > > < > > > : f 17 (v 1 , B 1 ) + f 12 (v 2 , B 2 ) + f 12 (v 3 , B 3 ) f 38 (v 1 , B 1 ) + min {f 18 (v 2 , B 2 ) + f 36 (v 3 , B 3 ), f 36 (v 2 , B 2 ) + f (v 3 , B 3 )} f 38 (v 1 , B 1 ) + min {f 39 (v 2 , B 2 ) + f 17 (v 3 , B 3 ), f 17 (v 2 , B 2 ) + f (v 3 , B 3 )} f 38 (v 1 , B 1 ) + f 39 (v 2 , B 2 ) + f 39 (v 3 , B 3 ) f 18 (v 1 , B) = f 18 (v 1 , B 1 ) + f 12 (v 2 , B 2 ) + f 12 (v 3 , B 3 ) Table 8: Case |V (K)| = 3 for RLDB. Function f 11 (v 1 , B) = min 8 > > > > > > > > > > > > < > > > > > > > > > > > > : f 36 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 18 (v j , B j ) + k P i=2 i =j f 17 (v i , B i ) 9 > = > ; f 39 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 18 (v j , B j ) + f 39 (v h , B h ) + k P i=2 i =j,h f 35 (v i , B i ) 9 > = > ; f 39 (v 1 , B 1 ) + k P i=2 f 35 (v i , B i ) f 12 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 17 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 18 (v j , B j ) + f 36 (v h , B h ) + k P i=2 i =j,h f 17 (v i , B i ) 9 > = > ; f 17 (v 1 , B 1 ) + min j,h,l=2,...,k j =h,j =l,h =l 8 > < > : f 18 (v j , B j ) + f 39 (v h , B h ) + f 39 (v l , B l ) + k P i=2 i =j,h,l f 35 (v i , B i ) 9 > = > ; f 18 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 36 (v h , B h ) + k P i=2 i =h f 17 (v i , B i ) 9 > = > ; f 18 (v 1 , B 1 ) + min h,l=2,...,k h =l 8 > < > : f 39 (v h , B h ) + f 39 (v l , B l ) + k P i=2 i =h,l f 35 (v i , B i ) 9 > = > ; k P i=1 f 12 (v i , B i ) f 17 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 39 (v h , B h ) + k P i=2 i =h f 35 (v i , B i ) 9 > = > ; f 13 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > : f 14 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 18 (v j , B j ) + k P i=2 i =j f 17 (v i , B i ) 9 > = > ; f 13 (v 1 , B 1 ) + k P i=2 f 17 (v i , B i ) f 37 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 18 (v j , B j ) + f 39 (v h , B h ) + k P i=2 i =j,h f 35 (v i , B i ) 9 > = > ; f 37 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 39 (v h , B h ) + k P i=2 i =h f 35 (v i , B i ) 9 > = > ; f 14 (v 1 , B) = min 8 > > > > > > > > > > > > < > > > > > > > > > > > > : f 36 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 18 (v j , B j ) + f 39 (v h , B h ) + k P i=2 i =j,h f 35 (v i , B i ) 9 > = > ; f 14 (v 1 , B 1 ) + k P i=2 f 17 (v i , B i ) f 36 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 39 (v h , B h ) + k P i=2 i =h f 35 (v i , B i ) 9 > = > ; f 15 (v 1 , B) = min 8 > > > > > < > > > > > : f 16 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 18 (v j , B j ) + k P i=2 i =j f 17 (v i , B i ) 9 > = > ; f 15 (v 1 , B 1 ) + k P i=2 f 17 (v i , B i ) f 16 (v 1 , B) = f 16 (v 1 , B 1 ) + k P i=2 f 17 (v i , B i ) Table 9: Case |V (K)| ≥ 4 for RLDB. Function f 17 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 17 (v 1 , B 1 ) + k P i=2 f 12 (v i , B i ) f 38 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 18 (v j , B j ) + f 36 (v h , B h ) + k P i=2 i =j,h f 17 (v i , B i ) 9 > = > ; f 38 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 39 (v h , B h ) + k P i=2 i =h f 17 (v i , B i ) 9 > = > ; f 38 (v 1 , B 1 ) + min j,h,l=2,...,k j =h,j =l,h =l 8 > < > : f 18 (v j , B j ) + f 39 (v h , B h ) + f 39 (v l , B l ) + k P i=2 i =j,h,l f 35 (v i , B i ) 9 > = > ; f 38 (v 1 , B 1 ) + min h,l=2,...,k h =l 8 > < > : f 39 (v h , B h ) + f 39 (v l , B l ) + k P i=2 i =h,l f 35 (v i , B i ) 9 > = > ; k P i=1 f 12 (v i , B i ) f 18 (v 1 , B) = f 18 (v 1 , B 1 ) + k P i=2 f 12 (v i , B i ) Table 10: Case |V (K)| ≥ 4 for RLDB.
Function Function ) 
f 19 (v 1 , B) = min 8 > > > < > > > : f 20 (v 1 , B 1 ) + f 27 (v 2 , B 2 ) f 19 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) f 22 (v 1 , B 1 ) + f 41 (v 2 , B 2 ) f 46 (v 1 , B 1 ) + f 23 (v 2 , B 2 ) f 24 (v 1 , B) = min ( f 25 (v 1 , B 1 ) + f 27 (v 2 , B 2 ) f 24 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) f 20 (v 1 , B) = min 8 > < > : f 20 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) f 23 (v 1 , B 1 ) + f 41 (v 2 , B 2 ) f 47 (v 1 , B 1 ) + f 23 (v 2 , B 2 ) f 25 (v 1 , B) = f 25 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) f 21 (v 1 , B) = min 8 > < > : f 27 (v 1 , B 1 ) + f 20 (v 2 , B 2 ) f 21 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) f 26 (v 1 , B 1 ) + f 40 (v 2 , B 2 ) f 26 (v 1 , B) = min ( f 26 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) f 48 (v 1 , B 1 ) + f 40 (v 2 , B 2 ) f 22 (v 1 , B) = min 8 > > > < > > > : f 23 (v 1 , B 1 ) + f 27 (v 2 , B 2 ) f 47 (v 1 , B 1 ) + f 42 (v 2 , B 2 ) f 22 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) f 46 (v 1 , B 1 ) + f 41 (v 2 , B 2 ) f 27 (v 1 , B) = f 27 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) f 23 (v 1 , B) = min ( f 23 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) f 47 (v 1 , B 1 ) + f 41 (v 2 , B 2 ) Table 11: Case |V (K)| = 2 for ROLDB. Function f 19 (v 1 , B) = min 8 > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > : f 20 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 23 (v 1 , B 1 ) + min{f 48 (v 2 , B 2 ) + f 42 (v 3 , B 3 ), f 42 (v 2 , B 2 ) + f 48 (v 3 , B 3 )} f 47 (v 1 , B 1 ) + min{f 48 (v 2 , B 2 ) + f 25 (v 3 , B 3 ), f 25 (v 2 , B 2 ) + f 48 (v 3 , B 3 )} f 22 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 41 (v 3 , B 3 ), f 41 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 46 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 23 (v 3 , B 3 ), f 23 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 19 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) f 22 (v 1 , B 1 ) + min{f 41 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 41 (v 3 , B 3 )} f 46 (v 1 , B 1 ) + min{f 23 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 23 (v 3 , B 3 )} f 46 (v 1 , B 1 ) + f 43 (v 2 , B 2 ) + f 43 (v 3 , B 3 ) f 20 (v 1 , B) = min 8 > > > > > > > > < > > > > > > > > : f 23 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 41 (v 3 , B 3 ), f 41 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 47 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 23 (v 3 , B 3 ), f 23 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 20 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) f 23 (v 1 , B 1 ) + min{f 41 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 41 (v 3 , B 3 )} f 47 (v 1 , B 1 ) + min{f 23 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 23 (v 3 , B 3 )} f 47 (v 1 , B 1 ) + f 43 (v 2 , B 2 ) + f 43 (v 3 , B 3 ) f 21 (v 1 , B) = min 8 > > > > > > > > > > < > > > > > > > > > > : f 26 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 20 (v 3 , B 3 ), f 20 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 27 (v 1 , B 1 ) + min{f 20 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 20 (v 3 , B 3 )} f 48 (v 1 , B 1 ) + f 41 (v 2 , B 2 ) + f 41 (v 3 , B 3 ) f 48 (v 1 , B 1 ) + f 47 (v 2 , B 2 ) + f 47 (v 3 , B 3 ) f 48 (v 1 , B 1 ) + min{f 43 (v 2 , B 2 ) + f 23 (v 3 , B 3 ), f 23 (v 2 , B 2 ) + f 43 (v 3 , B 3 )} f 21 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) + f 21 (v 3 , B 3 ) f 26 (v 1 , B 1 ) + min{f 40 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 40 (v 3 , B 3 )} f 22 (v 1 , B) = min 8 > > > > > > > > > > < > > > > > > > > > > : f 23 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 47 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 42 (v 3 , B 3 ), f 42 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 47 (v 1 , B 1 ) + min{f 42 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 42 (v 3 , B 3 )} f 46 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 41 (v 3 , B 3 ), f 41 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 22 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) f 46 (v 1 , B 1 ) + min{f 41 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 41 (v 3 , B 3 )} f 46 (v 1 , B 1 ) + f 43 (v 2 , B 2 ) + f 43 (v 3 , B 3 ) f 23 (v 1 , B) = min 8 > > > < > > > : f 47 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 41 (v 3 , B 3 ), f 41 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 23 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) f 47 (v 1 , B 1 ) + min{f 41 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 41 (v 3 , B 3 )} f 47 (v 1 , B 1 ) + f 43 (v 2 , B 2 ) + f 43 (v 3 , B 3 ) f 24 (v 1 , B) = min ( f 25 (v 1 , B 1 ) + min {f 27 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 24 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) f 25 (v 1 , B) = f 25 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) f 26 (v 1 , B) = min 8 > < > : f 26 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) + f 21 (v 3 , B 3 ) f 48 (v 1 , B 1 ) + min{f 40 (v 2 , B 2 ) + f 26 (v 3 , B 3 ), f 26 (v 2 , B 2 ) + f 40 (v 3 , B 3 )} f 48 (v 1 , B 1 ) + min{f 27 (v 2 , B 2 ) + f 20 (v 3 , B 3 ), f 20 (v 2 , B 2 ) + f 27 (v 3 , B 3 )} f 27 (v 1 , B) = f 27 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) + f 21 (v 3 , B 3 ) Table 12: Case |V (K)| = 3 for ROLDB. Function f 19 (v , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 20 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 27 (v j , B j ) + k P i=2 i =j f 26 (v i , B i ) 9 > = > ; f 23 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 48 (v h , B h ) + f 42 (v j , B j ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 47 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 48 (v h , B h ) + f 25 (v j , B j ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 22 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v j , B j ) + f 41 (v h , B h ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v j , B j ) + f 23 (v h , B h ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min j,h,l=2,...,k j =h,j =l,h =l 8 > < > : f 27 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + k P i=2 i =j,h,l f 45 (v i , B i ) 9 > = > ; f 19 (v 1 , B 1 ) + k P i=2 f 26 (v i , B i ) f 22 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 41 (v h , B h ) + k P i=2 i =h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 23 (v h , B h ) + k P i=2 i =h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min h,l=2,...,k h =l 8 > < > : f 43 (v h , B h ) + f 43 (v l , B l ) + k P i=2 i =h,l f 45 (v i , B i ) 9 > = > ; f 20 (v , B) = min 8 > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > : f 23 (v
f 43 (v i , B i )} f 21 (v , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 26 (v 1 , B 1 ) + min i,j,s=2,3,4,i =j,j =s,i =s {f 27 (v i , B i ) + f 20 (v j , B j ) + f 26 (vs, Bs)} f 26 (v 1 , B 1 ) + min j=2,3,4 {f 27 (v j , B j ) + P i=2,3,4,i =j f 41 (v i , B i )} f 26 (v 1 , B 1 ) + min j=2,3,4 {f 27 (v j , B j ) + P i=2,3,4,i =j f 47 (v i , B i )} f 26 (v 1 , B 1 ) + min i,j,s=2,3,4,i =j,j =s,i =s {f 27 (v i , B i ) + f 23 (v j , B j ) + f 43 (vs, Bs)} f 27 (v 1 , B 1 ) + min j=2,3,4 {f 20 (v j , B j ) + P i=2,3,4,i =j f 26 (v i , B i )} f 48 (v 1 , B 1 ) + f 43 (v 2 , B 2 ) + f 43 (v 3 , B 3 ) + f 43 (v 4 , B 4 ) f 48 (v 1 , B 1 ) + min j=2,3,4 {f 45 (v j , B j ) + P i=2,3,4,i =j f 41 (v i , B i )} f 48 (v 1 , B 1 ) + min j=2,3,4 {f 45 (v j , B j ) + P i=2,3,4,i =j f 47 (v i , B i )} f 48 (v 1 , B 1 ) + min i,j,s=2,3,4,i =j,j =s,i =s {f 23 (v i , B i ) + f 43 (v j , B j ) + f 45 (vs, Bs)} f 21 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) + f 21 (v 3 , B 3 ) + f 21 (v 4 , B 4 ) f 26 (v 1 , B 1 ) + min j=2,3,4 {f 40 (v j , B j ) + P i=2,3,4,i =j f 26 (v i , B i )} Table 13: Case |V (K)| = 4 for ROLDB. Function f 22 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > : f 23 (v 1 , B 1 ) + min j=2,3,4 {f 27 (v j , B j ) + P i=2,3,4,i =j f 26 (v i , B i )} f 47 (v 1 , B 1 ) + min i,j,s=2,3,4,i =j,j =s,i =s {f 26 (v i , B i ) + f 27 (v j , B j ) + f 42 (vs, Bs)} f 47 (v 1 , B 1 ) + min j=2,3,4 {f 42 (v j , B j ) + P i=2,3,4,i =j f 26 (v i , B i )} f 46 (v 1 , B 1 ) + min i,j,s=2,3,4,i =j,j =s,i =s {f 26 (v i , B i ) + f 27 (v j , B j ) + f 41 (vs, Bs)} f 46 (v 1 , B 1 ) + min j=2,3,4 {f 27 (v j , B j ) + P i=2,3,4,i =j f 43 (v i , B i )} f 22 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) + f 26 (v 4 , B 4 ) f 46 (v 1 , B 1 ) + min j=2,3,4 {f 41 (v j , B j ) + P i=2,3,4,i =j f 26 (v i , B i )} f 46 (v 1 , B 1 ) + min j=2,3,4 {f 45 (v j , B j ) + P i=2,3,4,i =j f 43 (v i , B i )} f 23 (v 1 , B) = min 8 > > > > > > > > > > < > > > > > > > > > > : f 47 (v 1 , B 1 ) + min i,j,s=2,3,4,i =j,j =s,i =s {f 26 (v i , B i ) + f 27 (v j , B j ) + f 41 (vs, Bs)} f 47 (v 1 , B 1 ) + min j=2,3,4 {f 27 (v j , B j ) + P i=2,3,4,i =j f 43 (v i , B i )} f 23 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) + f 26 (v 4 , B 4 ) f 47 (v 1 , B 1 ) + min j=2,3,4 {f 41 (v j , B j ) + P i=2,3,4,i =j f 26 (v i , B i )} f 47 (v 1 , B 1 ) + min j=2,3,4 {f 45 (v j , B j ) + P i=2,3,4,i =j f 43 (v i , B i )} f 24 (v 1 , B) = min 8 < : f 25 (v 1 , B 1 ) + min j=2,3,4 {f 27 (v j , B j ) + P i=2,3,4,i =j f 26 (v i , B i )} f 24 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) + f 26 (v 4 , B 4 ) f 25 (v 1 , B) = f 25 (v 1 , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) + f 26 (v 4 , B 4 ) f 26 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > : f 26 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) + f 21 (v 3 , B 3 ) + f 21 (v 4 , B 4 ) f 48 (v 1 , B 1 ) + min j=2,3,4 {f 40 (v j , B j ) + P i=2,3,4,i =j f 26 (v i , B i )} f 48 (v 1 , B 1 ) + min i,j,s=2,3,4,i =j,j =s,i =s {f 26 (v i , B i ) + f 27 (v j , B j ) + f 20 (vs, Bs)} f 48 (v 1 , B 1 ) + min j=2,3,4 {f 48 (v j , B j ) + P i=2,3,4,i =j f 41 (v i , B i )} f 48 (v 1 , B 1 ) + min j=2,3,4 {f 48 (v j , B j ) + P i=2,3,4,i =j f 47 (v i , B i )} f 48 (v 1 , B 1 ) + min i,j,s=2,3,4,i =j,j =s,i =s {f 23 (v i , B i ) + f 43 (v j , B j ) + f 48 (vs, Bs)} f 48 (v 1 , B 1 ) + f 43 (v 2 , B 2 ) + f 43 (v 3 , B 3 ) + f 43 (v 4 , B 4 ) f 27 (v 1 , B) = f 27 (v 1 , B 1 ) + f 21 (v 2 , B 2 ) + f 21 (v 3 , B 3 ) + f 21 (v 4 , B 4 ) Table 14: Case |V (K)| = 4 for ROLDB. Function f 19 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 20 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 27 (v j , B j ) + k P i=2 i =j f 26 (v i , B i ) 9 > = > ; f 23 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v h , B h ) + f 42 (v j , B j ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 23 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 42 (v j , B j ) + k P i=2 i =j f 26 (v i , B i ) 9 > = > ; f 47 (v 1 , B 1 ) + min j=2,...,k 8 > < > : f 25 (v j , B j ) + k P i=2 i =j f 26 (v i , B i ) 9 > = > ; f 22 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v j , B j ) + f 41 (v h , B h ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v j , B j ) + f 23 (v h , B h ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min j,h,l=2,...,k j =h,j =l,h =l 8 > < > : f 27 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + k P i=2 i =j,h,l f 45 (v i , B i ) 9 > = > ; f 19 (v 1 , B 1 ) + k P i=2 f 26 (v i , B i ) f 22 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 41 (v h , B h ) + k P i=2 i =h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min h=2,...,k 8 > < > : f 23 (v h , B h ) + k P i=2 i =h f 26 (v i , B i ) 9 > = > ; f 46 (v 1 , B 1 ) + min h,l=2,...,k h =l 8 > < > : f 43 (v h , B h ) + f 43 (v l , B l ) + k P i=2 i =h,l f 45 (v i , B i ) 9 > = > ; f 20 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 23 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v j , B j ) + f 41 (v h , B h ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 47 (v 1 , B 1 ) + min j,h=2,...,k j =h 8 > < > : f 27 (v j , B j ) + f 23 (v h , B h ) + k P i=2 i =j,h f 26 (v i , B i ) 9 > = > ; f 47 (v 1 , B 1 ) + min j,h,l=2,...,k j =h,j =l,h =l 8 > < > : f 27 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + k P i=2 i =j,h,l f 45 (v i , B i ) 9 > = > ; f 20 (v 1 , B 1 ) + k P i=2 f 26 (v i , B i ) f 23 (v 1 , B 1 ) + min h=2,...,k ( f 41 (v h , B h ) + P i=2,...,k,i =h f 26 (v i , B i ) ) f 47 (v 1 , B
f 21 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 26 (v
f 22 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 23 (v
f 25 (v 1 , B) = f 25 (v 1 , B 1 ) + k P i=2 f 26 (v i , B i ) f 26 (v 1 , B) = min 8 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : f 26 (v 1 , B 1 ) + k P i=1 f 21 (v i , B i ) f 48 (v

Figure 1 :

 1 Figure 1: A block graph where the black vertices form a minimum (a) ID-code, (b) LD-code, (c) OLD-code. 




  for some i and u = v r for some r. If r = 1, by using Lemma 8 (2) and the fact that C 1 is CO in any of the statements (i) to (v), it follows that v 1 and v are dominated and separated by C. Now, let r = 1. If i = 1 again Lemma 8 (2) together with the fact that v 1 ∈ C imply that v r and v are dominated and separated by C. 


Figure 2 :

 2 Figure 2: Illustration for the proof of Theorem 9, cases (ii) to (v). 




  are dominated and separated by C. From Lemma 4, u, v ∈ V (B) -k i=1 {v i } are dominated and separated by C. 




  are open-dominated and open-separated by C. From Lemma 4, if u, v ∈ V (B) -k i=1 {v i }, u and v are open-dominated and open-separated by C. Now,let u, v ∈ V (B), d(u, v) = 2 and u ∈ V (K). Then v ∈ V (B i ) -{v i } for some i and u = v r for some r.Assume first that r = 1. If i = 1, in (i) and (vii) C 1 is OLD. In the remaining cases, there exists h = 1 such that C h is CO. Hence, in any case, u and v are open-dominated and open-separated. Now, let i = 1. In (i), (ii), (iv), (vii) and (viii), C 1 is ADJ, thus u and v are open-dominated and openseparated. In (vi) and (x), {v h , v l } ⊆ N (u) ∩ C, but at most one of v h and v l is in N (v) ∩ C, thus u and v are open-dominated and open-separated. In 




  then u and v are open-dominated and open-separated. 




  then u and v are open-dominated and open-separated. Finally, let r = 1. If i = 1, as C 1 is CO in all the cases from (i) to (x), it holds that v 1 ∈ (N (u) ∩ C) -N (v) and u and v are open-dominated and open-separated. If i = 1, in (i), (ii) and (iii), C 1 is OF N and there exists w ∈ (N (v) ∩ C) -N (u) -{v 1 } and u and v are open-dominated and openseparated. In the remaining cases, C r is ADJ or there exists h = 1, r such that v h ∈ N (u) ∩ C, thus u and v are open-dominated and open-separated. Now, let u 




  and (vii) C 1 is OLD. In the remaining cases there exists h = 1 such that C h is CO, thus u and v are open-dominated and open-separated. If i = 1, in all the cases from (i) to (x) C 1 is CO and u and v are open-dominated and open-separated. Finally, let u = v i and v = v j for i = j. In all the cases from (i) to (x), C i and C j are CO or ADJ. Then u and v are open-dominated and open-separated. Corollary 16 With the notation of Theorem 15, we have the following: 


Function

  


•

  ID, CO, ADJ and FN, • ID, CO, ADJ and FN, • ID, CO, ADJ and FN, • ID, CO, ADJ and F N , • LD, CO, ADJ and FN, • LD, CO, ADJ and FN, • LD, CO, ADJ and F N , • OLD, CO, ADJ and OFN, • OLD, CO, ADJ and OF N , • OLD, CO, ADJ and OFN, • OLD, CO, ADJ and OF N , • OLD, CO, ADJ and OFN. 





  Let v 1 ∈ V (B) and let k be the order of a maximal clique containing v 1 .We will see that the algorithm RIDB needs to compute the main functions f j (v 1 , B) with j ∈ {1, . . ., 10}.Actually, for i ∈ {1, . . ., k} we need the list LID i that consists in functions f j (v i , B i ) for j ∈ {1, . . ., 10}.In order to do so we need the auxiliary functions f j (v i , B i ) for j ∈ {28, . . ., 34}.To see the correctness of our algorithm, let us prove first a technical lemma. 


	1: if v 1 has degree 0 in B then
	2: initialize LX (corresponding to problem X);
	3: else
	4: let K be a maximal clique with V (K) = {v 1 , . . . , v k } and delete its edges;
	5: let B 1 , . . . , B k be the remaining block graphs, resp., containing v 1 , . . . , v k ;
	6: let LX i = RXB(v i , B i ) for all i ∈ {1, . . . , k} corresponding to problem X;
	7: compute the main functions on (v 1 , B) from LX i for all i ∈ {1, . . . , k}
	corresponding to problem X.
	8: end if
	9: return the list LX of the values of the main functions f j on (v 1 , B)
	corresponding to problem X.
	4 A linear-time algorithm for the identifying code
	number of B
	Lemma 8 Consider a block graph B and V (K) = {v 1 , v 2 , . . . , v k }. Let C i be
	k
	a v i -almost identifying code in B i for i ∈ {1, 2, . . . , k} and C =
	i=1

9

  Consider a block graph B and V (K) = {v 1 , v 2 , . .., v k }.Let C be a code in B and C i = C ∩ V (B i ) for all i ∈ {1, 2, . .., k}.C 1 satisfies ID, CO, ADJ and F N , there exists j = 1 such that C j satisfies CO and ADJ, and C i satisfies CO and ADJ for all i = 1, j. (ii) C 1 satisfies CO, ADJ and F N , there exists j = 1 such that C j satisfies CO and ADJ, andC i satisfies ADJ for all i = 1, j. (iii) If k ≥ 3,C 1 satisfies CO, ADJ and FN, there exists hneq1 such that C h satisfies CO, there exists j = 1 such that C j satisfies CO and ADJ, and C i satisfies ADJ for all i = j. (iv) C 1 satisfies CO and FN, there exists h = 1 such that C h satisfies CO, and C i satisfies ADJ for all i = 1. (v) C 1 satisfies ID, CO, ADJ and FN, and C i satisfies CO and ADJ for all i = 1. Proof. Let C be a v 1 -almost identifying code in B with properties ID, CO, ADJ and F N . Observe that by Remark 3, C i is a v i -almost identifying code in B i for all i. Also, C 1 satisfies CO since C satisfies CO and v 1 


	Then C is a v 1 -almost
	identifying code in B with properties ID, CO, ADJ, FN if and only if C i is a
	v i -almost identifying code in B i for all i ∈ {1, 2, . . . , k}, and one of the following
	sets of assertions is satisfied:
	(i)



  is a v i -almost open locating-dominating code in B i for all i ∈ {1, 2, . . ., k} and one of the following sets of statements is satisfied.(i) C 1 is OLD, CO and OF N , there exists j = 1 such that C j is CO and ADJ, and C i is CO and ADJ for all i = 1, j. (ii) If k ≥ 3, C 1 is CO, ADJ and OF N , there exists h = 1 such that C h is CO, there exists j = 1, h such that C j is CO and ADJ, C i is CO and ADJ and for all i = 1, h, j. (iii) If k ≥ 3, C 1 is CO and OF N , there exists h = 1 such that C h is CO, there exists j = 1, h such that C j is CO and ADJ and OF N , and C i is CO and ADJ for all i = 1, j. (iv) If k ≥ 3, C 1 is CO, ADJ and OFN, there exists j = 1 such that C j is CO and ADJ, there exists h = 1, j such that C h is CO and ADJ, and C i is CO and ADJ for all i = 1, j, h. (v) If k ≥ 3, C 1 is CO and OFN, there exists j = 1 such that C j is CO and ADJ, there exists h = 1, j such that C h is CO, ADJ and OF N , and C i is CO and ADJ for all i = 1, j, h. (vi) If k ≥ 4, C 1 is CO and OFN, there exists j = 1 such that C 



almost open locating-dominating code in B having properties OLD, CO and OFN if and only if C i j is CO and ADJ, there exist h, l = 1, h = l such that C h , C l are CO, and C i is CO or ADJ for all i = 1, j, h, l. (vii) C 1 is OLD, CO and OFN, and C i is CO and ADJ for all i = 1. (viii) C 1 is CO, ADJ and OFN, there exists h = 1 such that C h is CO and ADJ, and C i is CO and ADJ for all i = 1, h. (ix) C 1 is CO and OFN, there exists h = 1 such that C h is CO, ADJ and OF N , and C i is CO and ADJ for all 


  , B 1 ) + f 26 (v 2 , B 2 ) + f 26 (v 3 , B 3 ) + f 26 (v 4 , B 4 ) f 23 (v 1 , B 1 ) + min 


	1 , B 1 ) +	min i,j,s=2,3,4,i =j,j =s,i =s	{f 26 (v i , B i ) + f 27 (v j , B j ) + f 41 (vs, Bs)}
	f 47 (v 1 , B 1 ) +	min i,j,s=2,3,4,i =j,j =s,i =s	{f 27 (v i , B i ) + f 23 (v j , B j ) + f 26 (vs, Bs)}
	f 47 (v 1 , B 1 ) + min j=2,3,4 {f 27 (v j , B j ) +	i=2,3,4,i =j P	f 43 (v i , B i )}
	f 20 (v 1 j=2,3,4 {f 41 (v j , B j ) +	i=2,3,4,i =j P	f 26 (v i , B i )}
	f 47 (v 1 , B 1 ) + min j=2,3,4 {f 23 (v j , B j ) +	i=2,3,4,i =j P	f 26 (v i , B i )}
	f 47 (v 1 , B 1 ) + min j=2,3,4 {f 45 (v j , B j ) +	P i=2,3,4,i =j



  43 (v h , B h ) + f 43 (v l , B l ) + 


	(				)
	1 ) + min h=2,...,k	f 23 (v h , B h ) +	i=2,...,k,i =h P	f 26 (v i , B i )
		8				9
	f 47 (v 1 , B 1 ) + min h,l=2,...,k h =l	> < > :	f k P i=2 i =h,l	f 45 (v i , B i )	> = > ;

Table 15 :

 15 Case |V (K)| ≥ 5 for ROLDB. 





  1 , B 1 ) + min j,h=2,...,k,j =h( f 27 (v j , B j ) + f 20 (v h , B h ) + P i=2,...,k,i =j,h f 26 (v i , B i ) 27 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + f 43 (vs, Bs) + 27 (v j , B j ) + f 41 (v h , B h ) + f 41 (v l , B l ) + 27 (v j , B j ) + f 47 (v h , B h ) + f 47 (v l , B l ) + 27 (v j , B j ) + f 43 (v h , B h ) + f 23 (v l , B l ) + f 26 (v 1 , B 1 ) + min h=2,...,k ( f 20 (v h , B h ) + P i=2,...,k,i =h f 26 (v i , B i ) f 43 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + f 48 (v1 , B 1 ) + min h,l=2,...,k,h =l ( f 41 (v h , B h ) + f 41 (v l , B l ) + P 


							)
				8		9
	f 26 (v 1 , B 1 ) +	min j,h,l,s=2,...,k j =h,j =l,j =s h =l,h =s,l =s	> < > :	f k P i=2 i =j,h,l,s	f 45 (v i , B i )	> = > ;
			8			9
	f 26 (v 1 , B 1 ) +	min j,h,l=2,...,k j =h,j =l,h =l	> < > :	f k P i=2 i =j,h,l	f 45 (v i , B i )	> = > ;
			8			9
	f 26 (v 1 , B 1 ) +	min j,h,l=2,...,k j =h,j =l,h =l	> < > :	f k P i=2 i =j,h,l	f 45 (v i , B i )	> = > ;
			8			9
	f 26 (v 1 , B 1 ) +	min j,h,l=2,...,k j =h,j =l,h =l	> < > :	f k P i=2 i =j,h,l	f 45 (v i , B i )	> = > ;
						)
			8			9
			> <		k	> =
	f 48 (v 1 , B 1 ) +	min j,h,l=2,...,k j =h,j =l,h =l	> :		P i=2 i =j,h,l	f 45 (v i , B i )	> ;

i=2,...,k,i =h,lf 45 (v i , B i ) ) f 48 (v 1 , B 1 ) + min h,l=2,...,k,h =l ( f 47 (v h , B h ) + f 47 (v l , B l ) + P i=2,...,k,i =h,l f 45 (v i , B i ) ) f 48 (v 1 , B 1 ) + min h,l=2,...,k, h =l ( f 43 (v h , B h ) + f 23 (v l , B l ) + P i=2,...,k,i =h,l f 45 (v i , B i ) ) k P i=1 f 21 (v i , B i ) f 26 (v1 , B 1 ) + min h=2,...,k ( f 40 (v h , B h ) + P i=2,...,k,i =h f 26 (v i , B i ) 
Table 16 :

 16 27 (v h , B h ) + f 42 (v j , B j ) + ,h=2,...,k,j =h ( f 27 (v j , B j ) + f 41 (v h , B h ) + P i=2,...,k,i =j,h f 26 (v i , B i ) 27 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + f 43 (v h , B h ) + f 43 (v l , B l ) + P i=2,...,k,i =h,l f 45 (v i , B i ) ) Case |V (K)| ≥ 5 for ROLDB. f 27 (v j , B j ) + f 41 (v h , B h ) + 27 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + 43 (v h , B h ) + f 43 (v l , B l ) + 


				8		9
		j,h=2,...,k j =h	> < > :	f k P i=2 i =j,h	f 26 (v i , B i )	> = > ;
			(		
	f 47 (v 1 , B 1 ) + min j=2,...,k	f 42 (v )
					8	9
	f 46 (v 1 , B 1 ) +	min j,h,l=2,...,k j =h,j =l,h =l	> < > :	f k P i=2 i =j,h,l	f 45 (v i , B i )	> = > ;
		k				
	f 22 (v 1 , B 1 ) +	P	f 26 (v i , B i )
		i=2				
			(			)
	f 46 (v 1 , B 1 ) + min h=2,...,k	f 41 (v j , B j ) +	i=2,...,k,i =h P	f 26 (v i , B i )
	f 46 (v 1 , B 1 ) +	min h,l=2,...,k,h =l
				29

1 , B 1 ) + min j=2,...,k ( f 27 (v j , B j ) + P i=2,...,k,i =jf 26 (v i , B i ) ) f 47 (v 1 , B 1 ) + min j , B j ) + P i=2,...,k,i =j f 26 (v i , B i ) ) f 46 (v 1 , B 1 ) + min j( k P i=2 f 26 (v i , B i ) 


  1 , B 1 ) + min 48 (v j , B j ) + f 41 (v h , B h ) + f 41 (v l , B l ) + 48 (v j , B j ) + f 47 (v h , B h ) + f 47 (v l , B l ) + 48 (v j , B j ) + f 23 (v h , B h ) + f 43 (v l , B l ) + 43 (v h , B h ) + f 43 (v l , B l ) + f 43 (vs, Bs) + 27 (v j , B j ) + f 43 (v h , B h ) + f 43 (v l , B l ) + f 43 (vs, Bs) + f 27 (v 1 , B) = f 27 (v 1 , B 1 ) + 


			8			9
			> <			k	> =
		h=2,...,k	> :	f 40 (v h , B h ) +	P i=2 i =h	f 26 (v i , B i )	> ;
				8	9
	f 48 (v 1 , B 1 ) +	min j,h=2,...,k j =h	> < > :	f 27 (v k P i=2 i =j,h	f 26 (v i , B i )	> = > ;
						8	9
	f 48 (v 1 , B 1 ) +	min j,h,l=2,...,k j =h,j =l,h =l	> < > :	f k P i=2 i =j,h,l	f 26 (v i , B i )	> = > ;
						8	9
	f 48 (v 1 , B 1 ) +	min j,h,l=2,...,k j =h,j =l,h =l	> < > :	f k P i=2 i =j,h,l	f 26 (v i , B i )	> = > ;
						8	9
	f 48 (v 1 , B 1 ) +	min j,h,l=2,...,k j =h,j =l,h =l	> < > :	f k P i=2 i =j,h,l	f 26 (v i , B i )	> = > ;
						8	9
	f 48 (v 1 , B 1 ) +	min h,l,s=2,...,k h =l,h =s,l =s	> < > :	f k P i=2 i =j,h,l	f 45 (v i , B i )	> = > ;
							8	9
	f 48 (v 1 , B 1 ) +	min j,h,l,s=2,...,k j =h,j =l,j =s h =l,h =s,l =s	> < > :	f k P i=2 i =j,h,l,s	f 45 (v i , B i )	> = > ;
			k			
		P	f 21 (v i , B i )
		i=2		

j , B j ) + f 20 (v h , B h ) + 
Table 17 :

 17 Case |V (K)| ≥ 5 for ROLDB.
Gabriela R Argiroffo, Silvia M Bianchi, Yanina Lucarini, Annegret K Wagler
Linear-time algorithms for three domination-based separation problems in block graphs