G Argiroffo

S Bianchi

Y Lucarini

Annegret Wagler
email: annegret.wagler@uca.fr

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 [START_REF] Lobstein | Watching systems, identifying, locating-dominating and discriminating codes in graphs[END_REF].

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. [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF]. 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] [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF]. 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 [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF] and remains hard for several graph classes where other in general hard problems are easy to solve, including bipartite graphs [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF] and two classes of chordal graphs, namely split graphs and interval graphs [START_REF] Foucaud | Identification, location-domination and metric dimension on interval and permutation graphs[END_REF].

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 [START_REF] Bertrand | Identifying and locating dominating codes on chains and cycles[END_REF], for stars [START_REF] Gravier | On graphs having a V {x}-set as an identifying code[END_REF], for complete multipartite graphs [START_REF] Argiroffo | Polyhedra associated with identifying codes in graphs[END_REF] and some subclasses of split graphs [START_REF] Argiroffo | Study of identifying code polyhedra for some families of split graphs[END_REF]). A linear-time algorithm to determine γ ID (G) if G is a tree was provided by Auger [START_REF] Auger | Minimal identifying codes in trees and planar graphs with large girth[END_REF].

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 [START_REF]Slater Dominating and location in acyclic graphs[END_REF][START_REF] Slater | Dominating and reference sets in a graph[END_REF]. 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 [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF] and even remains hard for bipartite graphs [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF]. This result is extended to planar bipartite unit disk graphs in [START_REF] Müller | Identifying and locating-dominating codes in (random) geometric networks[END_REF].

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 [START_REF] Slater | Dominating and reference sets in a graph[END_REF], cycles [START_REF] Bertrand | Identifying and locating dominating codes on chains and cycles[END_REF], stars, complete multipartite graphs and thin suns [START_REF] Argiroffo | A polyhedral approach to locating-dominating sets in graphs[END_REF]. Bounds for the LD-number of trees were provided in [START_REF] Blidia | Locating-domination and identifying codes in trees[END_REF], characterizations of trees with unique minimum locating-dominating sets were found in [START_REF] Blidia | Characterizations of trees with unique minimum locating-dominating sets[END_REF]. A linear-time algorithm to determine γ LD (G) if G is a tree was provided by Slater in [START_REF]Slater Dominating and location in acyclic graphs[END_REF].

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 [START_REF] Seo | Open neighborhood locating-dominating sets[END_REF]. 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)) [START_REF] Seo | Open neighborhood locating-dominating sets[END_REF]. 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 [START_REF] Seo | Open neighborhood locating-dominating sets[END_REF] and remains NP-hard for perfect elimination bipartite graphs and APXcomplete for chordal graphs with maximum degree 4 [START_REF] Pandey | Open Neighborhood Locating-Dominating Set in Graphs: Complexity and Algorithms[END_REF]. Closed formulas for the exact value of γ OLD (G) have been found so far only for restricted graph families such as cliques and paths [START_REF] Seo | Open neighborhood locating-dominating sets[END_REF], some algorithmic aspects are discussed in [START_REF] Panda | Algorithmic aspects of open neighborhood location domination in graphs[END_REF]. More results on all three problems are listed in [START_REF] Lobstein | Watching systems, identifying, locating-dominating and discriminating codes in graphs[END_REF]. 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 [START_REF] Bandelt | Distance-hereditary graphs[END_REF] resp. those chordal graphs in which every two maximal cliques have at most one vertex in common [START_REF] Howorka | On metric properties of certain clique graphs[END_REF].

We present linear-time algorithms for the three studied problems on block graphs, as a generalization of the linear-time algorithm by Auger [START_REF] Auger | Minimal identifying codes in trees and planar graphs with large girth[END_REF] 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 [START_REF] Seo | Open neighborhood locating-dominating sets[END_REF] 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 [START_REF] Argiroffo | A linear-time algorithm for the identifying code problem on block graphs[END_REF].

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 [START_REF] Auger | Minimal identifying codes in trees and planar graphs with large girth[END_REF]. 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 [START_REF] Argiroffo | Study of identifying code polyhedra for some families of split graphs[END_REF].

γ 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,[START_REF] Foucaud | Identification, location-domination and metric dimension on interval and permutation graphs[END_REF][START_REF] Gravier | On graphs having a V {x}-set as an identifying code[END_REF][START_REF] Howorka | On metric properties of certain clique graphs[END_REF][START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF]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 [START_REF] Auger | Minimal identifying codes in trees and planar graphs with large girth[END_REF] 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,l

f 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 (v

1 , 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 =j

f 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.


published or not. The documents may come

Magnetic approaches to form and to stimulate three-dimensional tissue models


Guilhem Mariotte

Ludovic Leclercq

Humberto Gonzalez Ramirez

Jean Krug

Cecile Becarie

Investigating the compliance of travelers with the recommendation of socially desirable alternatives

Keywords: Advanced Urban Traffic Control, Human Behavior, Route Choice Experiment, Social Optimum, User Compliance

The development of Advanced Traveler Information Systems (ATIS) with enroute navigation systems has opened the door to new traffic regulation policies such as collective route guidance based on the minimization of total travel time. However, a critical element for their efficiency is the compliance of travelers with route recommendations. In this paper, we use a stated preference survey based on route choice situations from a real network to investigate traveler compliance for different levels of travel time sacrifice vs several social benefits. Two kinds of social benefits are considered: congestion alleviation and emission reduction. The data collected allows us to precisely quantify the travel time sacrifice that a given proportion of travelers would be ready to accept in order to take a different alternative that has a given level of social benefit. In line with the literature, our analysis confirms the decrease of compliance with the increase of sacrifice. Moreover, it suggests that the way the recommendation is intended could play a significant role in the level of compliance: the display of an advice message for the social path (in the congestion alleviation case) is shown to be more efficient than only showing additional information (in the emission reduction case).

INTRODUCTION

Now that en-route navigation systems are a common feature of individual cars, Advanced Traveler Information System (ATIS) technologies can influence travelers' decisions by providing real-time travel information. This is promising to design new control policies such as route guidance [START_REF] Oh | Parametric evaluation for route guidance systems with analysis of sustainable driver compliance[END_REF][START_REF] Angelelli | Proactive route guidance to avoid congestion[END_REF][START_REF] Wang | A real-time vehicle-specific ecorouting model for on-board navigation applications capturing transient vehicle behavior[END_REF]. Notably, while individual-centered information can jam the network in a sub-optimal User Equilibrium (UE) state, it may also lead it towards a System Optimum (SO) if the ATIS technology is properly designed to favor system optimal routes, as shown in theoretical studies by [START_REF] Dia | Modelling drivers' compliance and route choice behaviour in response to travel information[END_REF][START_REF] Colak | Understanding congested travel in urban areas[END_REF]Klein et al., 2018;[START_REF] Van Essen | From user equilibrium to system optimum: a literature review on the role of travel information, bounded rationality and non-selfish behaviour at the network and individual levels[END_REF][START_REF] Van Essen | Travelers' compliance with social routing advice: Impacts on road network performance and equity[END_REF]. However, one of the critical element of an efficient route guidance system is the compliance of travelers, who may be willing to act for the common good but are faced with recommendations that go against their selfish individual goals. Understanding and estimating traveler compliance was notably done by [START_REF] Kerkman | Car drivers' compliance with route advice and willingness to choose socially desirable routes[END_REF][START_REF] Djavadian | Empirical evaluation of drivers' route choice behavioral responses to social navigation[END_REF][START_REF] Ringhand | Make this detour and be unselfish! influencing urban route choice by explaining traffic management[END_REF]Klein & Ben-Elia, 2018;[START_REF] Van Essen | Travelers' compliance with social routing advice: evidence from sp and rp experiments[END_REF]. As highlighted in these works, the compliance of travelers with social advice is higher when in-depth information is provided to them about the recommendation motivations and expected benefits, in comparison to a basic advice message. These studies also greatly contributed to the understanding of the trade-off travelers can make between their own interests and more socially desirable detours. In particular, [START_REF] Van Essen | Travelers' compliance with social routing advice: evidence from sp and rp experiments[END_REF] proposed a joint regression model from a questionnaire and a field experiment with revealed choices to analyze the impact of factors such as travel time and advice contents to explain the compliance of drivers towards a social optimum.

In contrast to the existing works mentioned above, in which generally only a global measure of compliance is given, in this study we focus on the detailed quantification of compliance to better identify when users stop complying with advice due to competition with other selfish goals. We also want to observe to which extent the level of expected social benefit can counterbalance selfishness. This leads to the following research question: What is the sacrifice that travelers are ready to accept to improve social welfare? Here, we define the sacrifice as the relative increase of travel time a user expects to face by taking the recommended path instead of traveling on the shortest path. As for the notion of social welfare, we choose to focus on two major aspects: (i) the improvement of overall traffic flow (expressed as the reduction of total traveled time), and (ii) the reduction of CO 2 emissions. Our aim is to test multiple urban configurations with different origindestination (OD) pairs and different total lengths, in order to propose a wide range of travel time sacrifices and social benefits.

METHODOLOGY

Our stated preference study uses a Matlab application which automatically and successively generates path choice situations for the respondent. Each path choice situation corresponds to the layout in Figure 1. Three paths, P1, P2 and P3 are proposed, whose expected travel times are such that T T 1 < T T 2 < T T 3 . P1 is thus the shortest path (denoted by the abbreviation ShP), and it is expected to be the usual choice of users if the travel time is the only information provided. The travel time sacrifice ∆T T j of path j is written as follows ( j = 1, 2 or 3):

∆T T j = T T j -T T 1 T T 1 (1)
The experiment was split into four successive sessions, as presented in Table 1. The travel time information was given in all sessions. Sessions 1 and 2 referred to the first sub-question on congestion alleviation. Session 1 was the control experiment (without recommendation), and session 2 included a recommendation on either P2 or P3 for each path choice presented to the participant. The recommended path (P2 or P3) was thus explicitly defined as the social path (abbreviated by SoP). This new information was given by highlighting the social path and displaying a recommendation message with the value of the social benefit: the total traveled time (TTT in short) relative reduction ∆T T T red . Sessions 3 and 4 referred to the second sub-question on emission reduction. Here, P3 was shown as a public transport alternative (PT in short). Session 3 was the control experiment (with only travel time information), and session 4 included the additional CO 2 emission information on all paths. As a public transport option, P3 had the lowest emission and was thus implicitly defined as the social path. In this case, the value of social benefit was defined as the relative reduction of CO 2 emission compared to the shortest path P1. In this paper, we propose a new definition of traveler compliance. To account for the prior preferences of users (who may not be choosing the shortest path whatever the recommendation), we define the compliance as the ratio of the number of users who changed their choices for the social path between the control and recommendation experiments over the number of users who were previously traveling on the other paths (not that which would be turned into SoP) in the control experiment. Let us suppose that p 0 j is the proportion of users on path j during the control experiment and p j the proportion during the recommendation experiment. Then, for the first sub-question (congestion alleviation), in the control experiment (session 1) the proportion of users traveling on possible social paths is p 0 2 + p 0 3 because either P2 or P3 will be turned into SoP. In the recommendation experiment (session 2), the proportion actually traveling on the social path is precisely p j with j = SoP. Therefore, with our definition, the compliance κ is written as:

κ = p j=SoP -p 0 2 -p 0 3 1 -p 0 2 -p 0 3 (2)
Similarly, for the second sub-question (emission reduction), in the control experiment (session 3) the proportion of users traveling on possible social paths is p 0 3 , as only P3 will be turned into SoP. In the recommendation experiment (session 4), the proportion actually traveling on the social path is therefore p 3 . Thus, in this case the compliance corresponds to:

κ = p 3 -p 0 3 1 -p 0 3 (3)

RESULTS AND DISCUSSION

133 participants from various ages and social backgrounds were recruited from October to December 2019. On average, each participant made 32 path choices per session, thus 128 choices for the four sessions. With all the participants, each session gathered around 4300 choice observations, thus around 17,200 observations for the four sessions. To observe the evolution of compliance in the different sessions, the choices of participants are aggregated with respect to similar intervals of sacrifice and benefit. 1.0 q q q q q q q q q q q q travel time sacrifice ∆TTj observed choice freq/compliance For the first sub-question on congestion alleviation, Figure 2(a) presents the compliance κ in session 2 (solid line) as calculated with the social path choice frequency in session 2 (dashed line) and the observed choice frequency of P2 and P3 in session 1 (dotted line), see also equation 2. Four values of choice frequency are calculated for four intervals of travel time sacrifice (each dot corresponds to the middle of each ∆T T j interval). We used only four points to ensure enough observations in each travel time interval to obtain a reliable measure of choice frequency. As expected, the compliance decreases as the sacrifice increases, but several key observations are noteworthy. First, we noticed very high compliance (κ ≈ 0.8) for a low sacrifice (∆T T j ≈ 0.1). This can be interpreted in the light of the Bounded Rationality theory [START_REF] Simon | A behavioral model of rational choice[END_REF]: easily accepting a path change at a low cost may denote an indifference or satisficing behavior. Second, the decrease of compliance is surprisingly almost linear. Nevertheless, a quicker drop in compliance is visible around ∆T T j = 0.3, which may suggest a threshold where the sacrifice starts overcoming the social benefit. The compliance is reduced by half when the travel time of the social path is around 50% higher than that of the shortest path. Figure 2(b) depicts the same compliance evolution but now distinguished by the social benefit level displayed in the recommendation message (TTT relative reduction, ∆T T T red ). Overall, we observed higher compliance for a higher benefit, which was in line with expectations. However, an interesting trend is worth mentioning. For low sacrifice (∆T T j ≈ 0.1), the benefit value plays a significant role from ∆T T T red = 0.05 to 0.1, but is irrelevant for higher TTT reductions, meaning that the advice itself seems more important than its contents at this point. This is also the case for a sacrifice above ∆T T j = 0.3, where the benefit values of ∆T T T red = 0.05 to 0.1 lead to the same compliance level. However, higher values of ∆T T T red = 0.15 to 0.2 still have a positive effect on compliance even for high sacrifice levels. This means that only significant global gains were considered worthy by users when the sacrifice was high. The threshold here seems to be around 15% of total traveled time reduction. 1.0 q q q q q q q q q travel time sacrifice ∆TTj observed choice freq/compliance P3 (session 3) SoP = P3 (session 4) Compliance (session 4) For the second sub-question on emission reduction, Figure 3(a) presents the compliance in session 4 (solid line) as calculated with the social path (P3) choice frequency in session 4 (dashed line) and the observed choice frequency of P3 in session 3 (dotted line), see also equation 3. Here only three values of choice frequency are calculated for three intervals of travel time sacrifice, due to data sampling problems in obtaining reliable estimations of choice frequency. Notable differences from the previous sub-question case can be pointed out. First, we see a clear mode preference for public transport, as suggested by the high choice frequency of P3 in session 3. Second, compliance is much lower in session 4 in comparison to session 2, due to this mode preference. Likewise, and as expected, compliance decreases with the increase of sacrifice, but the decrease is much slower when compared to session 2. Hence, the definition of a threshold is almost impossible in this case. Putting aside the effect of mode preference, this suggests a clear difference in the perception of the social path between the two sub-questions. Whereas the effect of the advice message is immediate but rapidly decreases with travel time sacrifice in session 2, the CO 2 emission information seems less sensitive to the level of sacrifice. This perception difference is further confirmed when looking at Figure 3(b), which depicts the evolution of compliance in session 4 for various levels of CO 2 emission reduction (compared to the emission of P1). Unlike session 2, the effect of the social benefit value is very clear in session 4. A low relative reduction of emission has no effect (CO 2 reduction of 0.3), whereas a larger emission reduction (0.6 to 0.9) leads to an obvious increase of compliance.

CONCLUSIONS

In this paper, we analyzed a stated preference survey to understand and measure the competition between selfish goals and social objectives when faced with a path choice situation with recommendation. The results showed different reactions for two social objectives: (i) congestion alleviation and (ii) emission reduction. For the first one, we observed a high impact of the recommendation when the sacrifice was low, which may be explained by a satisficing behavior [START_REF] Simon | A behavioral model of rational choice[END_REF]. Compliance then quickly drops as the sacrifice increases. The value of the congestion reduction in the advice message was found to be significant in moving travelers to the social path, albeit quite subtly. However, for the second social objective, the role of the emission reduction value was clearer: a significant reduction was required to show a significant impact on compliance. It was surprisingly less sensitive to the increase in sacrifice. Notable differences between the two cases also played a role: the social path was a public transport alternative and the recommendation was implicit by showing lower emissions for this path. In our participant set, a natural preference for public transport mode also explained the lesser effect of the emission information. This study must still be confirmed by other findings from real situations, as the stated intentions of travelers are always likely to be more optimistic than the revealed choices of the same travelers. Nevertheless, our findings could contribute to the design of route guidance policies to set thresholds of sacrifice and benefits to ensure a given level of compliance.

Figure 1 :

 1 Figure 1: Screenshot of the application. A path choice situation is characterized by the following information: (1) map visualization, (2) departure time, (3) transport mode, (4) travel time and sometimes CO 2 emission, and (5) sometimes a recommendation message.

Figure 2 :

 2 Figure 2: Compliance for the first sub-question addressed by sessions 1 and 2. (a) Global compliance for the social path ( j = SoP), and (b) compliance by value of social benefit (relative reduction of total traveled time).

Figure 3 :

 3 Figure 3: Compliance for the second sub-question addressed by sessions 3 and 4. (a) Global compliance for the social path ( j = SoP), and (b) compliance by value of social benefit (relative reduction of CO 2 emissions).

Table 1 :

 1 The four sessions of the path choice experiment.

				Session
	Path	First sub-question on	Second sub-question on
	characteristics	congestion alleviation	emission reduction
		1	2	3	4
	ShP	P1	P1	P1	P1
	SoP	-	P2 or P3	-	P3
	PT	-	-	P3	P3
	Travel time info	all paths	all paths	all paths	all paths
	TTT red message	-	SoP	-	-
	CO 2 info	-	-	-	all paths

Acknowledgment

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No 646592 -MAGnUM project). The authors are thankful to all the lab members who helped the data collection by recruiting new participants and assisting them during the experiment: Delphine Lejri, Manon Seppecher, Omar Rifki, Mahendra Paipuri and Mostafa Ameli.