I Caragiannis

A Ferreira

C Kaklamanis

S Pérennes

H Rivano

Fractional Path Coloring in Bounded Degree Trees with Applications *

Keywords: Fractional coloring, path coloring, linear relaxation, approximation algorithms, wavelength division multiplexing, optical networks, fixed parameter tractable problem

This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a 1 + 5/3e ≈ 1.61-approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) optical networks.

Introduction

Given a graph, the fundamental graph coloring problem (also known as vertex coloring) is to assign colors to vertices in such a way that adjacent vertices are assigned different colors and the number * A preliminary version of this paper appears in Proceedings of the 28th International Colloquium on Automata, Languages and Programming, Crete, Greece, 2001. This work was supported in part by the European Union under IST FET Project AEOLUS.

† Computer Technology Institute, 61 Riga Feraiou str., Patras, Greece.

‡ MASCOTTE Project, CNRS-I3S-INRIA, B.P. 93, 06902 Sophia Antipolis, France. A.Ferreira is currently on leave as Head of Science Operations at the COST Office, Brussels, http://www.cost.esf.org. Corresponding author:

Herve.Rivano@sophia.inria.fr.

1 of colors used is minimized. In general, graph coloring is hard to solve to optimality or even to approximate [START_REF] Hochbaum | Approximation Algorithms for N P -Hard Problems[END_REF].

A related problem, the path coloring problem, consists in coloring a set P of paths on a graph G so that two paths sharing an arc (if the graph is directed) or an edge of G have different colors. This problem is equivalent to coloring the corresponding conflict graph, which is the undirected graph in which the vertices correspond to the paths of P and are joined by an edge if the corresponding paths share an arc (or edge) of G. Notice, however, that this problem was proven to be the same as standard graph coloring in terms of complexity or difficulty to approximate, since any n-vertex graph is the conflict graph of a set of paths of an n × n grid [START_REF] Chlamtac | Lightpath communications: An approach to high bandwidth optical WAN's[END_REF]. Furthermore, path coloring was proved to be N P-hard even when G is a tree [START_REF] Tarjan | Decomposition by clique separators[END_REF].

This problem has many applications in wavelength division multiplexing (wdm) optical networks and call scheduling, which have recently triggered a renewed interest in path coloring on special classes of graphs. In such applications, one is given an optical network with n nodes and a multiset of point-to-point communication requests, and must assign to each request a lightpath and to each lightpath a color (wavelength) so that conflicting lightpaths (i.e., lightpaths using the same link) are assigned different colors. The goal is to minimize the number of colors used. This problem (known as the wavelength routing problem) has been widely studied in the literature [START_REF] Auletta | Randomized path coloring on binary trees[END_REF][START_REF] Bermond | Efficient collective communication in optical networks[END_REF][START_REF] Erlebach | Optimal wavelength routing on directed fiber trees[END_REF][START_REF] Ferreira | On the design of multifiber WDM networks[END_REF][START_REF] Tucker | Coloring a family of circular arcs[END_REF]. It has been proved to be difficult (N P-hard even for rings [START_REF] Tucker | Coloring a family of circular arcs[END_REF]), and one can show that there exist networks with O(n 2 ) vertices and n requests on which it is hard to decide if the optimal number of colors is either 1 or n. Thus, in general, the problem is also hard to approximate. In the case where the lightpaths have already been assigned to requests, the problem is known as the wavelength assignment problem (wap).

This problem can be reduced to coloring directed paths of a directed graph (since optical transmissions are one-way) usually symmetric. Note that there are important differences between the directed and the undirected version of the problem; for instance, the problem can be solved in polynomial time in symmetric directed stars, but is in N P-hard for undirected stars [START_REF] Golumbic | The edge intersection graphs of paths in a tree[END_REF].

Our work focuses on fractional directed path coloring on symmetric directed graphs, a natural linear programming relaxation of directed path coloring. We first remark that a coloring of directed paths is a covering of the paths by independent sets of directed paths. The relaxation arises when the independent sets may have fractional weights [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]. In this paper we prove exact and approximation results for directed path coloring and fractional directed path coloring in directed symmetric graphs. Unless otherwise specified, we shall use the terms paths and graphs to denote directed paths and symmetric directed graphs, respectively.

Previous work

Recently, several papers studied path coloring on simple networks like meshes, rings and trees [START_REF] Auletta | Randomized path coloring on binary trees[END_REF][START_REF] Bermond | Efficient collective communication in optical networks[END_REF][START_REF] Erlebach | Optimal wavelength routing on directed fiber trees[END_REF][START_REF] Gargano | Colouring paths in directed symmetric trees with applications to WDM routing[END_REF][START_REF] Kumar | Approximating arc circular colouring and bandwidth allocation in all-optical ring networks[END_REF][START_REF] Niessen | The round-up property of the fractional chromatic number for proper circular arc graphs[END_REF]. Most of the results study the relationship between the load of the set of paths (i.e., the maximum number of paths crossing an arc) and the number of colors of an optimal coloring. Notice that the load is a lower bound for the optimal number of colors.

For rings (where the problem is indeed the classical circular arc coloring problem), a 3 2 approximation was proposed in [START_REF] Karapetyan | On coloring of arc graphs[END_REF]; this approximation ratio was recently improved to 1 + 1 e ≈ 1.37 [START_REF] Kumar | Approximating arc circular colouring and bandwidth allocation in all-optical ring networks[END_REF]. This latter result exploits a reduction of the circular arc coloring problem to a special instance of integral multicommodity flow problem [START_REF] Tucker | Coloring a family of circular arcs[END_REF]. The coloring is obtained by first solving the multicommodity flow problem with fractional numbers and then performing a randomized rounding of this solution.

For trees, a polynomial time deterministic algorithm which colors any set of paths of load l has been designed and proved to use at most 5l/3 colors [START_REF] Erlebach | Optimal wavelength routing on directed fiber trees[END_REF]. This algorithm is greedy and proceeds in phases, one per each node v of the tree. The nodes are considered following their breadthfirst numbering. The phase associated with node v assumes that there is already a partial proper coloring where all paths that touch (i.e., start, end, or go through) nodes with numbers strictly smaller than v's have been colored and no other path has been colored. It has also been proved that this algorithm is optimal within the class of greedy deterministic algorithms [START_REF] Erlebach | Optimal wavelength routing on directed fiber trees[END_REF].

Recently, a different approach has been followed for binary trees giving rise to a randomized algorithm [START_REF] Auletta | Randomized path coloring on binary trees[END_REF]. Instead of greedily computing a solution from top to bottom, this algorithm actually keeps a distribution of solutions (it computes from top to bottom one random element of the distribution). With high probability, an element of the distribution have the particularity to look locally random that is when considering the restriction of the distribution to each star composing the tree. This implies a kind of "average case" of the greedy deterministic algorithm and, hence, an improvement of the approximation ratio. This algorithm colors any set of paths of load l on a binary tree using at most 7l/5 + o(l) colors, with high probability. The hidden constants in the lower order terms are huge and are due to the integrality constraints of the problem and the random choices of the algorithm.

Note that these two results approximate the optimal number of colors within 5/3 and 7/5+o(1), respectively.

A recent survey of results on the path coloring problem in trees has recently been published [START_REF] Caragiannis | Approximation Algorithms for Path Coloring in Trees[END_REF].

Our results

Our approach, detailed in Section 2, is based on the fact that the graph coloring problem is equivalent to assigning unit cost to some independent sets of the graph such that all vertices are covered (i.e., are contained in an independent set of unit cost) and the total cost (i.e., the number of independent sets of unit cost) is minimized.

We then observe that Kumar's fractional solution [START_REF] Kumar | Approximating arc circular colouring and bandwidth allocation in all-optical ring networks[END_REF] gives in fact an optimal fractional coloring of paths in the ring. Notice, however, that this relaxation is generally also hard to approximate in general graphs.

The positive side of our observation is that it allows us to prove several results related to integral and fractional path coloring, as follows.

• In Section 3 we show that fractional path coloring in bounded degree trees can be solved in polynomial time. This result is constructive, i.e., our algorithm recursively builds in polynomial time a polynomial size linear program whose final solution is such an optimal fractional coloring. For this we introduce the notion of trace of a coloring, which encodes a local and aggregate snapshot of the coloring of the paths crossing each edge (or pair of opposite arcs). Using the traces, we are able to explore the exponential number of different fractional colorings in polynomial time.

• This fractional path coloring algorithm for trees can be easily adapted to any bounded-degree graph with bounded-treewidth, as described in Section 4.1.

• We show an upper bound of 7l/5 for the fractional path chromatic number in binary trees in terms of the load l of the set of paths (see Sections 4.2 and 4.3). This is somewhat related to the results in [START_REF] Auletta | Randomized path coloring on binary trees[END_REF], since their randomized algorithm can be seen as an attempt to emulate a balanced fractional coloring and, conversely, a balanced fractional coloring can be interpreted as a perfect random sample of their algorithm. However, the analysis of our algorithm is easier, our algorithm is deterministic, and our bound is tighter. Note that a tighter upperbound of 1.336l has been shown for the specific case of locally symmetric set of paths on binary trees [START_REF] Caragiannis | Fractional and Integral Coloring of Locally-Symmetric Sets of Paths on Binary Trees[END_REF].

• With respect to integral path coloring, in Section 5 we provide a randomized approximation algorithm for path coloring in bounded-degree trees with approximation ratio 1.61+o(1). This is done by applying randomized rounding to the fractional solution presented in Section 3. A subsequent work has recently tighten the approximation ratio to 1.511 + o(1) [START_REF] Caragiannis | Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks[END_REF].

In the following section we recall the formal definitions of (fractional) coloring and (fractional) path coloring.

Fractional coloring

The graph coloring decision problem is usually considered as deciding on input of a graph G and an integer k, whether it is possible to find a mapping from the vertices to a given set of k colors such that no two adjacent vertices are mapped to the same color. The related optimization problem consists of minimizing k, the size of the color set. In other words, the coloring problem is a constrained packing of the vertices into the set of colors. One can then express it as a polynomial size integer linear program (denoted ilp), but unfortunately its linear relaxation gives no practical information for building good integral solutions.

On the other hand, the coloring problem can also be seen as a covering problem. Recall that a covering of the vertices by a collection of covering sets is a subset of the collection such that each vertex belongs to at least one of the selected covering set. In the following we explain that the coloring problem is the problem of finding a minimum cost covering of the vertices by independent sets.

Vertex coloring as a covering problem

In a graph coloring problem, a set of vertices that can be mapped to the same color does not include any pair of adjacent vertices. We remark that this is the definition of an independent set of the graph. Therefore, a coloring of the vertices is a family of independent sets (the colors or, equivalently, the sets of vertices mapped to a common color) such that any vertex belongs to exactly one of these independent sets. In other words and defining the cost of a family of sets as the sum of the costs of each set, finding an optimal coloring of the graph is equivalent to finding a minimum cost integral partition of the vertices into independent sets of unit cost (i.e. each vertex belongs to exactly one independent set).

Furthermore, a covering which is not a partition (i.e. at least one vertex belongs to more than one independent set) induces a partition of cost at most the cost of the covering, since any subset of an independent set is still an independent set. Therefore, the graph coloring problem is also equivalent to finding a minimal cost integral covering of the vertices by independent sets of unit cost.

Given a graph G = (V, E), this means solving the following integer linear program:

minimize I∈I x(I) subject to I∈I:v∈I x(I) ≥ 1 ∀ v ∈ V x(I) ∈ {0, 1} ∀ I ∈ I
where I denotes the collection of the independent sets of G and variable x(I) is set to 1 if the independent set I belongs to the coloring (i.e. is a color), 0 otherwise. Although this ilp may have an exponential number of variables (one per independent set), its linear relaxation will be useful in the following. When the weights over the independent sets are no longer constrained to integrality, the problem can be written as the following linear program:

minimize I∈I x(I) subject to I∈I:v∈I x(I) ≥ 1 ∀ v ∈ V 0 ≤ x(I) ≤ 1 ∀ I ∈ I
The corresponding combinatorial problem is called the fractional coloring problem [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF], and the cost of an optimal solution is called fractional chromatic number, denoted χ f (G).

If x is a cost function over the independent sets of the graph G satisfying the constraints of the above linear program, we call it a fractional coloring of G. We use the symbol x(G) to denote the cost of the solution x.

In general, the fractional chromatic number is as hard to approximate as the chromatic number up to a logarithmic factor since Lovász's theorem on fractional covers [START_REF] Lovász | On the ratio of optimal integral and fractional covers[END_REF] states that any ρ-approximation of the fractional chromatic number leads to a ρ • log(n)-approximation of the chromatic number. Note that the logarithmic factor is negligible from a complexity point of view since the chromatic number is non-approximable within n 1-ǫ for all ǫ > 0 [START_REF] Feige | Zero Knowledge and the Chromatic Number[END_REF].

Notwithstanding, this approach is very useful if we use duality results, as follows.

Lemma 1 Computing the fractional chromatic number is polynomially equivalent to solving the maximum weighted independent set problem.

Proof: It is well-known that the dual of the linear program of a covering problem is the linear program of the packing problem where there is a constraint per variable of the primal and a variable per primal constraint. Therefore, the dual of the linear program of the fractional coloring problem is the following [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]:

maximize v∈V y(v) subject to v∈I y(v) ≤ 1 I ∈ I y(v) ≥ 0
Let us define the weight of an independent set I ∈ I as the sum of the weights of its vertices:

y(I) = v∈I y(v).
In this dual problem, a nontrivial constraint is violated if and only if the weight of one independent set I is greater than 1. Hence, the maximum weighted independent set problem (mwis) is a separation oracle for this last problem. According to the separation and optimization equivalence ( [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF], Th. 4.2.7), the dual of fractional coloring and the mwis are equivalent up to a polynomial reduction. Moreover, by duality, computing the fractional chromatic number and the optimum of its dual are polynomially equivalent. Hence the lemma.

Note that this duality argument does not provide any effective fractional coloring algorithm, but rather a way to compute the fractional chromatic number in specific cases.

On the positive side, we can notice that in the dual linear program, some constraints are obviously useless. If I is a maximal independent set for inclusion, any independent set J ⊆ I will induce a constraint parallel to (considered as a cut hyperplane of the linear program's polytope), and less restrictive than the one induced by I. This means that for a maximal independent set of size s, 2 s -1 constraints are useless and could be dropped from the linear program, hence removing an exponential number of constraints. The intuition is then that the huge number of constraints of the dual (or, equivalently, variables of the primal) may not be a drawback when solving some classes of this problem.

The extension of the definition of fractional coloring to fractional path coloring is given below. We also show that the fractional path chromatic number of paths in bounded-degree trees can be computed in polynomial time using Lemma 1.

Fractional path coloring

As stated in the Introduction, the vertex coloring and path coloring are equivalent problems, since coloring a set of paths in a graph is equivalent to coloring the corresponding conflict graph, defined below.

Definition 1 Given G a symmetric directed graph, and P a set of paths in G, the conflict graph of P in G is the graph whose vertices represent the paths of P and where there is an edge between vertices representing paths sharing an arc of G.

We are now able to extend some terms of graph coloring to path coloring. Given a set of paths P in a graph G, we define an independent set of paths as a set of pairwise arc-disjoint paths, i.e., a set of paths whose corresponding vertices form an independent set of the conflict graph1 . We can hence define the fractional path coloring problem analogously to the vertex coloring problem.

Definition 2 Given G a graph and P a set of paths in G, an optimal fractional coloring of P is a minimum cost fractional covering of the paths by independent sets of unit cost.

The corresponding linear program is the same as the fractional vertex coloring, and Lemma 1 still holds. We will denote by χ(G, P) (χ f (G, P)) the (fractional) path chromatic number of P on G. We will also denote by l(G, P) the load of P on G, i.e. the maximum number of paths of P using any given arc of G.

As far as the relationship between χ and χ f is concerned, the following result is implicit in the work of Kumar [START_REF] Kumar | Approximating arc circular colouring and bandwidth allocation in all-optical ring networks[END_REF], which addresses the case of the n-nodes ring, denoted by C n :

χ(C n , P) ≤ χ f (C n , P) + l(C n , P) e + o(l(C n , P)).
In this context, e is the well-known Neper constant.

In the very specific case where the conflict graph is a proper circular arc graph, Niessen and Kind [START_REF] Niessen | The round-up property of the fractional chromatic number for proper circular arc graphs[END_REF] proved that χ = ⌈χ f ⌉.

In the following we prove that computing the fractional chromatic number of a set of paths in a bounded-degree tree can be done in polynomial time.

Theorem 2 Given T a bounded-degree tree and P a set of paths in T , the fractional chromatic number of P in T , χ f (T , P), can be computed in polynomial time.

Proof: Lemma 1 claims the polynomiality equivalence between the computation of the fractional chromatic number and the maximum weighted independent set.

Considering that T is rooted at any given vertex r, the maximum weighted independent set of P in T is obtained by a call to an algorithm proposed and prooved polynomial by Garg [START_REF] Garg | Multicommodity Flows and Approximation Algorithms[END_REF][START_REF] Garg | Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees[END_REF]. This algorithm is reproduced as Algorithm 1.

This result proves that it is possible to compute the fractional chromatic number of a set of paths in a bounded-degree tree in polynomial time, but does not give an algorithm to obtain a Algorithm 1 Garg's algorithm: mwis algorithm for paths P in a tree T Input: T v subtree of T rooted at node v, d v number of children of v, r root of T Input: On each arc, a "void" path of length 1 is defined and denoted ∅ Ouput: mwis of paths P in a T and its weight Data: ∀v, p, q, I[v, p, q] mwis of paths in T v with paths p, q touching v oppositely Data: w[v, p, q] weight of I[v, p, q] not counting w(p) nor w(q) for all node v such that its children have been processed do for all paths p, q touching v oppositely do let c j , j = 1 . . . d v , be the

j th child of v I[v, p, q] ← ∅, w[v, p, q] ← 0
for all P = {p j , q j , j = 1 . . . d v } s. t. p, q ∈ P and ∀j, p j , q j touch both v and c j do w(P ) ← ρ∈P \{p,q} w(ρ) {p and q are not counted}

if w(P ) + j w[c j , p j , q j ] > w[v, p, q] then I[v, p, q] ← ∪ j I[c j , p j , q j ], w[v, p, q] ← w(P ) + j w[c j , p j , q j ] mark v as processed Return I[r, ∅, ∅], w[r, ∅, ∅]
corresponding fractional coloring. The main argument of the proof is the fact that the dynamic programming tables generated by the algorithm have size O(l 2d ), where l is the load of the set of paths and d the maximum degree of the tree.

Moreover, due to the exponential number of variables involved in the fractional coloring linear program, it is not straightforward to design a strategy relying on the fractional chromatic number to compute an optimal fractional coloring. Nevertheless, we give in the following section an algorithm which builds a small linear program in order to effectively produce solutions of the fractional path coloring problem in bounded-degree trees. The strategy of our algorithm is closely related to Garg's algorithm: our linear program is based on subproblems that are exponential in the degree of the tree.

An algorithm for fractional path coloring in bounded-degree trees

In this section we study the fractional path coloring problem in trees. We denote a path going from node u to v by (u v), and a path going from u to v using the arc (a, b) by (u a → b v). The special path ∅ denotes a non-existent or void path on any arc.

The main idea of our algorithm is to recursively build a linear program of polynomial size. In the following we will prove that two fractional path colorings of two subtrees can be merged into one for the whole tree if and only if they coincide on the arc where they overlap. This may still yield an exponential algorithm since there may exist an exponential number of different fractional path colorings on an arc. In order to cope with this difficulty, we define an aggregate coding of the "behavior" of a coloring on a pair of opposite arcs, or edge, called the trace of this coloring.

Trace of a fractional coloring

Given a tree T , and a solution for path coloring that is a weight function x on the independent sets of paths in the tree T , we define the trace of the fractional coloring x on an edge e as the function X e : P 2 → R, defined as follows.

• For any path p, let I(p) be the set of independent sets containing p, and let I(p, q) = I(p) ∩ I(q).

• Let I e (p, ∅) be the set of independent sets where only p crosses e. Let I e (∅, ∅) be the set of independent sets not using e.

• For any pair of paths p, q crossing e in opposite directions, let the trace variable for p and q on e be X e (p, q) = I∈I(p,q) x(I).

The trace function is a local and aggregate snapshot of the fractional coloring. Local, because only the paths going through the edge e are considered and two different colorings may have the same trace if their difference does not affect the coloring of these paths. Aggregate, because the trace function does not code all the weights of the independent sets, only sums of these variables. In the following we will show that this loss of information is not critical, even if it allows to code an exponential number of different colorings with polynomial size objects.

The trace X of the fractional coloring x is the set of the trace functions on all edges of T :

X = {X e , ∀e ∈ T }.
Given an instance of fractional path coloring (T , P) and a constant c, we denote by T r c (T , P) the set of all the fractional colorings of (T , P) with cost less than c.

Split and merge

Our algorithm proceeds by recursively constructing a polynomial size linear program whose solution provides a fractional coloring. Our induction is based on merge and split procedures which allow to build any instance of fractional path coloring starting from instances on stars (i.e. a tree where only one vertex has degree larger than 1) and merging them step by step.

Consider a fractional path coloring of (T , P), where T is not a star and such that e = {u, v} is a non-terminal edge of T . The splitting of T on edge e yields two smaller instances of fractional path coloring, denoted (T 0 , P 0 ) and (T 1 , P 1 ), as described by Algorithm 2 (cf. Figure 1 for an illustration). Note that the split procedure of any fractional coloring of T with cost c induces fractional colorings on (T 0 , P 0 ) and (T 1 , P 1 ) with cost less than c. From construction of the split procedure, both have the same trace on e.

The split procedure is reverted by the merge procedure, described in Algorithm 3 and working as follows. Once two subproblems are generated by the split of (T , P) into (T 0 , P 0 ) and (T 1 , P 1 ), if a fractional coloring is computed on each subproblem such that they have the same trace on the splitting edge e, the merge builts a fractional coloring of (T , P), as proved in proposition 3. Now, we prove that any element of T r c (T , P) can be obtained from one element of T r c (T 0 , P 0 ) and one of T r c (T 1 , P 1 ).

Proposition 3

The set of all possible merging of elements of T r c (T 0 , P 0 ) and T r c (T 1 , P 1 ) is included in T r c (T , P) and is empty if and only if T r c (T , P) is empty.

Proof: Given two fractional colorings x0 ∈ T r c (T 0 , P 0 ) and x1 ∈ T r c (T 1 , P 1 ) having the same trace X e 0 and X e 1 on e, the merge procedure (Algorithm 3) applied to x0 and x1 produces an element of T r c (T , P). To verify this claim, just note that this procedure preserves the following invariants at each step:

• Paths are covered either by x0 , x1 or x;

• x(P) + x0 (P 0 ) = x(T, P) + x1 (P 1 ) = c. Algorithm 2 split (T , P) on e into (T 0 , P 0 ) and (T 1 , P 1 )

Input: e = {u 0 , u 1 } non-terminal edge of T (V i , E i ) ← connected components of T \ e ∋ u i , i = 0, 1 T i ← (V i ∪ {u 1-i }, E i ∪ {e}), i = 0, 1 for all p ∈ P do if ∃i, p ∈ U i then P i ← p else if ∃i, p = (a u i → u 1-i b), a ∈ U i , b ∈ U 1-i then P i ← p = (a u 1-i ) P 1-i ← p = (u i b)
Algorithm 3 merge x0 ∈ T r c (T 0 , P 0 ), x1 ∈ T r c (T 1 , P 1 ) into x ∈ T r c (T , P) Input: Trace equality on edge e = {u 0 , u 1 }: X e 0 = X e 1 , and P i = {p T i , p ∈ P} Ouput: X e = X e 0 = X e 1 ∀ I ∈ I, x(I) is implicitly initialized with value 0.

while ∃p 0 , q 0 ∈ P 0 ∪ {∅}|X e 0 (p 0 , q 0 ) = 0 do {Trace equality ensures ∃p, q ∈ P, p 0 = p |T 0 , q 0 = q |T 0 and X e 1 (p |T 1 , q |T 1 ) > 0} select I 0 ∈ I 0 (p 0 , q 0 ) such that x0 (I 0 ) > 0 select I 1 ∈ I 1 (p |T 1 , q |T 1 ) such that x1 (I 1 ) > 0 xmin ← min (x 0 (I 0 ), x1 (I 1 ))

I ← I 0 \ {p 0 , q 0 } ∪ I 1 \ {p |T 1 , q |T 1 } ∪ {p, q} {By construction I ∈ I} increase x(I)

by xmin decrease xi (I i ) by xmin {Ensures trace equality}

It follows that, at the end of the main loop, x is a fractional coloring of (T , P) with cost c. Moreover, for i = 1, 2, the trace of x on any edge of T equals the trace of xi in T i . Therefore, the set of all possible merging of elements of T r c (T 0 , P 0 ) and T r c (T 1 , P 1 ) is included in T r c (T , P).

Moreover, as stated before, the split of any element of T r c (T , P) produces two elements of T r c (T 0 , P 0 ) and T r c (T 1 , P 1 ) that can be merged together into an element of T r c (T , P).

Corollary 4

We can compute a polynomial size linear program whose solutions are valid traces of elements of T r c (T , P).

Proof: We first assume that such a program exists for bounded degree d stars. We then use a recursive algorithm to generate a linear program whose solutions are traces of T r c (T , P). Assume that T can be split on edge e into (T 0 , P 0 ) and (T 1 , P 1 ) and let S 0 (S 1 ) be the linear program for traces of T r c (T 0 , P 0 ) (T r c (T 1 , P 1 )), where we assume that the trace on e is associated to the variables X e 0 (p, q) and X e 1 (p, q). Then, a system for (T , P) is:

S = S 0 ∪ S 1 ∪ {X e 0 (p, q) = X e 1 (p, q) | ∀p, q}
Therefore, if l denotes the load of the set of paths, there are O(l 2 ) constraints per edge of the tree (the trace equality constraints) and one system per star, i.e. per non-terminal node of the tree. If s is a bound on the size of a linear program for a star, the size of our linear program is then O n(l 2 + s) .

A naïve way to get a polynomial size linear program for the bounded-degree d stars case is to set one variable per independent set, which are polynomial in number, as explained below.

The number of paths composing an independent set is obviously at most 2d and there are at most 2dl paths in a bouded degree d star whose load is l. Therefore, the number of independent sets composed of i paths is at most 2dl i ≤ (2dl) 2d . Consequently, there are less than 2d(2dl) 2d = O(l 2d ) independent sets on a bounded degree d star of load l, and as many variables in the linear program.

Fractional coloring is trivially described from these variables, and each trace variable is obtained, by definition, as the addition of some of these variables.

Proposition 5 Fractional path coloring in bounded-degree d trees can be reduced to solving a polynomial size linear program.

Proof: We simply have to show how to compute an element of T r c (T , P) from a trace X of an element of T r c (T , P) (obtained from Corollary 4). Again we proceed inductively: we start from stars and find for each one a fractional coloring having the trace that X induces on it. Then, if (T , P) can be split into (T 0 , P 0 ) and (T 1 , P 1 ), Proposition 3 provides a way to merge fractional colorings of (T 0 , P 0 ) and (T 1 , P 1 ), when their traces are equal, and this is the case since they are subsets of X.

Fractional coloring is Fixed Parameter Tractable

Note that the model above induces very large systems, since we could get O(nl 6 ) variables for binary trees, and O(nl 8 ) for ternary ones. In this section we show that fractional path coloring on trees is FPT [START_REF] Flum | Parameterized Complexity Theory[END_REF]. Indeed, by identifying the independent sets of a the paths on a star to a perfect matching of the complete bipartite graph, one can describe the trace variable on a star with flow equations.

It is therefore possible to reduce the system size to O(dM (d)l 2 n), that is polynomial in the problem size, while exponential only in the parameter d. Proof: First, and without loss of generality, we assume that the load is uniform. Corollary 4 shows that the size of the linear program of the fractional path coloring of (T , P) of cost less than c is O(nl 2 ) plus the sum of the sizes of the linear programs for each star of the tree T , which is less than n times the size for a star of degree d.

Then, remark that if each possible path is present exactly once (what we will call a canonical d-star), then the set of all independent sets loading each arc exactly once (canonical independent sets) is isomorphic to the set of the perfect matchings in K d,d . Let M (d) denote the size of this set and note that M (d) depends only on d.

It is possible to describe the polytope of the matching of this bipartite graph with simple flow equations [START_REF] König | Graphok és matrixok[END_REF], as follows.

Let us consider a star S = {v 0 , v 1 , . . . , v d } ⊆ T , where v 0 is the center of S and d its degree. Arcs of S are {(v 0 , v i ), (v i , v 0 ), ∀i ∈ [1, . . . , d]}. Let M be the set of independent sets of load 1 of S. For all M ∈ M, we build an auxiliary flow network M , as follows.

-For each path p ∈ T including a path of M , we add a vertex V (p) to F M .

-For each pair of vertices V (p), V (q) such that

∃ i ∈ [1, . . . , d] | (v 0 , v i ) ⊆ p and (v i , v 0 ) ⊆ q,
we add the arc (V (p), V (q)) to F M .

-We define a flow function 2 f M on the arcs of F M which induces a flow function f ′ M on its vertices.

-For each leaf v i of the star we add to

F M the constraint on f ′ M p|(v 0 ,v i )⊆p f ′ M (V (p)) = c M .
Any solution to the previous system induces a covering of the paths with weight f ′ (p) and a subpart of the trace of value f (p, q).

The total system for a star is obtained as follows.

-The flow equations for each matching M ∈ M : define f M variables; -X(p, q) = M ∈M f M (p, q) : computation of the trace variables; -

M ∈M f ′ M (p) ≥ 1 : covering of the paths; - M ∈M c M ≤ c : cost constraint.
Due to the above mentioned property of the matching polytope, this system describes the fractional coloring problem for a star with an encoding of the trace variables.

It follows that the fractional coloring of each star of T can be described with a system of size at most M (d)(= |M|) times l 2 d. Hence, the system for T is of size O(dM (d)l 2 n).

Notice that an optimal fractional coloring can be computed in polynomial time even if the degree of the tree is d = O(max{log l/ log log l, log n/ log log n}), since M (d) = O(d!).

Extensions and applications

In this section we extend the technique described in the previous section to bounded degree graphs with bounded treewidth.

Furthermore, we obtain an algorithm for fractional path coloring on binary trees with cost at most 7l/5. Using the results for the fractional path coloring, we achieve improved approximation algorithms for the path coloring problem in bounded-degree trees and bounded-degree trees of rings, and upper bounds for the path chromatic number in terms of the fractional path chromatic number and the load.

2 By flow function we mean conservative for vertices. One can note that this function is a circulation since no sink and no source are present.

Some polynomial instances

In the case of bounded degree graphs with bounded treewidth, we obtain the following.

Proposition 7 Fractional path coloring can be solved in polynomial time in bounded degree graphs with bounded treewidth.

Proof: The proof follows similar lines with Section 3. Consider a tree-decomposition of the graph of width bounded by a given constant k ′ . An "edge" of the tree-decomposition is a cut of the graph that is also upper-bounded by a given k = Ω(k ′2 ) (see [START_REF] Bondy | Graph Theory[END_REF] for details). A node of the tree is a set of Ω(k ′ ) vertices of the initial graph.

One can then define trace variables on each edge of the decomposition of size bounded by O(l 2k ) and build a polynomial size linear program.

Fractional path coloring on binary trees

Fractional path coloring on binary trees can be performed using a particular coloring, called balanced coloring, where the traces depend only on the number of paths going trough an arc. Definition 3 For any given constant w ∈ [0, 1], a w-balanced coloring of a set of paths is a fractional path coloring such that the trace function over any arc e is w l(e) for all paths using this arc. I.e., X e (p, q) = w l(e)

, X e (p, ∅) = 1w, ∀e, ∀p, q paths using e in opposite directions.

This particular kind of fractional path coloring will help us to exhibit an upper bound on the cost of a fractional path coloring on binary trees.

Corollary 8 For any given constant w ∈ [0, 1], any set of paths P in any binary tree T can be w-balanced colored by independently coloring all the restrictions of P to each of the ternary stars composing T .

Proof: If one performs independent local colorings of all the ternary stars composing T , then, by definition of the w-balanced coloring, the trace equality equations of the linear program built in Section 3 are respected. Therefore, as stated in the proof of Proposition 5, one can find a global fractional coloring consistent with the local colorings using the merge procedure.

Moreover, the cost of such a w-balanced coloring is the maximum, over all the ternary stars composing T , of the local w-balanced colorings.

A simple but exhaustive analysis shows that ternary stars can be colored in a balanced way with at most 7 5 l colors -detailed in the next section -, this yields the following Proposition.

Proposition 9 For any set of paths P of load l(T, P) on a binary tree T , there exists a fractional coloring of cost at most 7l(T,P)

5

. Moreover, such a fractional coloring can be computed in polynomial time.

This result is proved in Section 4.3, by showing that there exists a 4 5 -balanced coloring of P with cost at most 7l(T,P) 5 for any set of path P on any ternary star T . As a corollary, we obtain that given a set of paths P on a binary tree T , the maximum independent set of paths of P has size at least 5|P| 7l(T,P) .

Balanced fractional coloring of ternary stars

This section is dedicated to the case analysis of the w-balanced coloring of paths in ternary stars.

In order to get an upper bound of the cost of any balanced coloring, we first define reduced 3-stars. A generic set of paths in a ternary star can be described by 12 parameters as depicted in Figure 2. This is too large to permit an exhaustive case study. In order to make such an analysis tractable, we use a standard reduction [START_REF] Auletta | Randomized path coloring on binary trees[END_REF], Algorithm 4, which transforms any ternary star into a reduced 3-star which is described by only 3 parameters.

a i + b i + d i = l out,i a 2 + b 1 + c0 = l in,0 a 0 + b 2 + c 1 = l in,1 a 1 + b 0 + c 2 = l in,2 ∀i, l in,i ≤ l, l out,i ≤ l
Algorithm 4 Reduction of a set of paths P in a ternary star

Input: Central vertex = n c , leaves = n i , i = 0, 1, 2
Let l be the load of P for all under-loaded arc e do add paths of length 1 on e to reach load l repeat select p, path of length 1 from n i to n c select q, path of length 1 from n c to n j , j = i concatenate p and q into a path (n i → n c → n j )

until there are no more paths to concatenate

The resulting reduced 3-star, depicted in Figure 3, has a more compact description than the generic one, allowing an analysis which will give an upper bound on the cost of the fractional coloring of any ternary star. Proof: Algorithm 4 first adds paths of length 1 in order to equalize the load. This step can only increase the cost of the coloring. Once the load is uniform there is a flow conservation law at the central vertex of the star since each edge supports the same amount of paths in both directions.

The repeat-until loop terminates in at most 3l steps since there are at most 3l paths arriving at the central vertex and one is processed at each step. The loop terminates when there are no more paths to concatenate, which means that all remaining paths of length 1 are found on only one link, say the link between n 0 and n c without loss of generality. Moreover, the loop maintains the flow conservation since each step concatenates one path arriving at the central vertex with one leaving it. Therefore, it is obvious that there are exactly the same amount, γ, of paths of length 1 in each direction (from n 0 to n c and from n c to n 0 ).

The resulting set of paths is then a convex combination of 3 kinds of independent sets: the counter-clockwise ((n 0 → n 1 → n 2 ), α of them) and clockwise ((n 0 → n 2 → n 1 ), β of them) circuits, and the set with 2 paths of length 1, (n 0 → n c ) and (n c → n 0 ), and 2 paths of lengths 2, (n 1 → n 2 ) and (n 2 → n 1 ) (γ of them), as depicted in Figure 3. Therefore, the 3 parameters α, β, and γ are enough to describe the resulting set.

The cost of the coloring of the resulting set is greater or equal to the original one since the concatenation cannot decrease it.

We can identify the parameters of the reduced star with the one of the generic star, as follows.

a 0 = a 2 = α, b 0 = b 1 = β, d 0 = c 0 = γ, a 1 = α + γ, b 1 = β + γ.
In the following, a pair of paths crossing an edge on opposite direction is called a doublon.We say that a path touches a vertex v if it starts, ends, or go through v. Definition 4 At a vertex n i , a doublon is a couple of non-void paths touching n i in opposite directions. A half-doublon is a non-void path touching n i associated with the void path ∅ in the opposite direction.

The definition of a w-balanced fractional coloring requires that on each link the trace variable for any pair of paths using the link oppositely equals w l . In other words, any doublon has to be covered with weight w l . Consequently, the half-doublon have to be covered with weight 1w. The actual list of the doublons and half-doublons of a reduced 3-star is described in Appendix A. Based on this list, Appendix B describe the numbers of independent sets of paths that are used in a balanced coloring of such a reduced 3-star. The cost of such a coloring implies the result stated as proposition 9 : For any set of paths P of load l(T, P) on a binary tree T , there exists a fractional coloring of cost at most 7l(T,P) 5 .

Proof of proposition 9

The proof consists in showing that any set of paths on any binary tree admits a balanced coloring with cost at most 7l 5 . A detailled construction of such a coloring for paths on a reduced 3-star is given in Appendix B. Corollary 8 and Lemma 10 complete the proof.

Note that this result seems highly related to the randomized algorithm in [START_REF] Auletta | Randomized path coloring on binary trees[END_REF], which colors paths in binary trees with 7l 5 + o(l) colors, but at the time of this writing no formal equivalence has been proven.

Integral path coloring in trees

In this section we present an important application of our methods to the path coloring problem in trees.

Note that the result of [START_REF] Erlebach | Optimal wavelength routing on directed fiber trees[END_REF] states that there exists a polynomial time algorithm which colors any set of paths P of load l(T, P) on a tree T with at most 5l(T, P)/3 colors. Since the load l(T, P) is a lower bound for the optimal number of colors, this gives a 5/3-approximation algorithm. In the following we exploit the optimal solution for the fractional path coloring which can be obtained in polynomial time for bounded degree trees to design a randomized algorithm with better approximation ratio.

Given a solution x of the fractional path coloring of the set of paths P on a tree T , the idea is to perform a randomized rounding to x and obtain an integral solution x. After rounding, x may not be a feasible solution to the path coloring problem since some of the constraints of the form I∈I:p∈I x(I) ≥ 1 may be violated. However, this is a feasible solution to the path coloring problem on the set of paths P ′ ⊆ P, defined as the set of paths contained in independent sets I such that x(I) = 1. This means that we have properly colored some of the paths of P with χ f (T , P) colors.

After this rouding procedure, a set of paths P\P ′ remains to be colored. The analysis presented in [START_REF] Kumar | Approximating arc circular colouring and bandwidth allocation in all-optical ring networks[END_REF] for a similar procedure in circular arc graphs holds. The procedure is a balls and bins-like algorithm that defines a martingale sequence for the set of colored paths. Following Azuma's inequality [START_REF] Azuma | Weighted sum of certain dependent random variables[END_REF], we therefore obtain that if l(T , P) = Ω(log n), where n is the number of vertices in T , then after the rounding procedure the load of paths in P\P ′ is l(T , P\P ′ ) ≤ l(T , P) e + o(l(T , P)), with high probability. Now, we can apply the algorithm of [START_REF] Erlebach | Optimal wavelength routing on directed fiber trees[END_REF] to color the paths in P\P ′ with 5l(T ,P) 3e

+ o(l(T , P)) additional colors. In total, we use at most χ f (T , P) + 5l(T , P) 3e + o(l(T , P))

colors. Since l(T, P) ≤ χ f (T, P) ≤ χ(T, P), we obtain the following results.

Proposition 11 There exists a randomized 1.61 + o(1)-approximation algorithm to the path coloring problem in bounded-degree trees.

Corollary 12 For any set of paths P on a tree T , it holds: χ(T, P) ≤ χ f (T, P) + 5l(T, P) 3e + o(l(T, P)).

Note that using a much more sophisticated parameterized randomized rounding, a (1.511+o(1))approximation randomized algorithm has been proposed in [START_REF] Caragiannis | Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks[END_REF].

We can also apply similar arguments to bounded degree trees of rings to obtain a 2.22approximation algorithm. For that, an optimal fractional coloring is computed and randomly rounded as above. The remaining set of paths is colored as if it was a set of paths on the tree obtained by contracting each ring into an bi-directed edge. This transformation obviously doubles the load of the set of path and over-constrained the coloring. Following the same proof as above, such a coloring is bounded by χ f + 5.2l 3e + o(l).

Further application and research

Our research in this paper was motivated by questions related to the design of wavelength division multiplexing optical networks. Many applications of our techniques to wdm networks can be foreseen, like in branch and bound methods, or in the design of multifiber networks.

A recent paper exploits similar techniques in the more general settings of the approximate strong separation problem [START_REF] Jansen | Approximate strong separation with application in fractional graph coloring and preemptive scheduling[END_REF]. In this paper, applications to task and call scheduling issues are discussed. Since then, more sophisticated rounding techniques have improved the approximation ratios of integral coloring [START_REF] Caragiannis | Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks[END_REF], but the main ideas are the same.

The approximation results presented in this paper, as well as the best known in the literature, show a gap between the cost of integral and fractional path coloring in trees while there are no tight negative results.

We conjecture that this gap is small and that a 1 + o(1) randomized approximation may even exist. Indeed, randomized rounding strategies like those developed in [START_REF] Auletta | Randomized path coloring on binary trees[END_REF] or [START_REF] Caragiannis | Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks[END_REF] but based on an optimal fractional coloring might be quite efficient. The main challenge is then to characterize the distribution defined by the traces of optimal fractional colorings, which is still open.

A Description of the doublons of a reduced 3-star

This appendix is dedicaded to the description and counting of all the doublons and half-doublons that are to be covered by a balanced coloring of reduced 3-star.

We define the type of (half-)doublon depending on the paths composing it and give the number present on each vertex.

• A doublon of type:

B Balanced coloring of a reduced 3-star

This Appendix is dedicated to the main step in the proof of proposition 9. We show that any reduced 3-star admits a path coloring with cost at most 7l 5 , where l = α + β + γ is the load of the set of paths. In the following we build a w-balanced coloring where w = 4 5 and compute its cost.

B.1 Description of the independent sets

This coloring uses independent sets in order to cover the doublons defined and enumerated in Appendix A with weight weight w l (1w for half-doublons). In particular, one can note that building a w-balanced coloring requires the use of some non-maximal sets.

The shape of the independent sets that we use is closely related to the characterization of the doublons they cover. Hence, their names are used interchangeably. The actual weight that has to be put on each shape of independent set is described in the following tables , as well as the type of (half-)doublons that they cover at each vertex of the star. One can check that, given the choice of w = 4 5 , all the doublons and half-doublons described in Appendix A are covered with the relevant weight.

The cost of the coloring is then the sum of the weights of all the independent sets in these tables.

For the sake of readability, let us define The cost of the coloring depends on the values of the two max. Three cases have to be considered: none, one or both max is null. (1), ( 2) and ( 3) put together show that any reduced 3-star admits a coloring of cost upperbounded by 7l 5 . This coloring is a 4 5 -balanced coloring.

Figure 1 :

 1 Figure 1: Splitting a tree on e.

Proposition 6

 6 Fractional path coloring in bounded-degree d trees can be reduced to solving a linear program of size O(dM (d)l 2 n).

Figure 2 :

 2 Figure 2: The generic 3-star and its parameters.

Figure 3 :

 3 Figure 3: The generic reduced 3-star

1 . 0 n 1 , 2 : 2 n 0 n 1 , 2 :

 10122012 A is 2 paths in a counter-clockwise circuit; n 0 : α 2 , n 1,2 : α(α + γ)2. B is 2 paths in a clockwise circuit; n 0 : 2 , n 1,2 : β(β + γ) 3. C is two paths of length 1; n 0 : γ 2 4. D i is two parallel paths of length 2 not touching vertex n i ; D 0 n 1,2 : (α + γ)(β + γ) D 1 n 0,2 : αβ D 2 n 0,2 : αβ 5. E i , i = 1, 2,is a path of length 1 and a path touching vertex n i in a counter-clockwise circuit; n 0 : αγ each 6. F i , i = 1, 2, is a path of length 1 and a path touching vertex n i in a clockwise circuit; n 0 : βγ each.• A half-doublon of type:1. A ∅ i is a path not touching vertex n i in a counter-clockwise circuit; A ∅ 0,1 : α 2. B ∅ i is a path not touching vertex n i in a clockwise circuit ; B ∅ ∅ + is a path of length 1 from n 0 to n c ; n 0 : γ 4. C ∅ -is a path of length 1 from n c to n 0 . n 0 : γ.

G 1 )0 n 1 n 2 IS n 0 n 1 n 2

 122 A = min (1w)α, (1w)(α + γ)αγ w l and G B = min (1w)β, (1w)(β + γ)βγ w l Maximal independent sets IS n Quantity Quantity

1 . 2 - 2 . 4 ≤ 7 5 l 3 .= ( 2 -

 122432 If αγ w l -(1w)γ > 0 and βγ w l -(1w)γ > 0, using ab ≤ (a+b) 2lγ + γ 2 ) + wγγ 2 w l -2γ + wγ ≤ (2w)l + wl 4 If αγ w l -(1w)γ > 0 and βγ w l -(1w)γ < 0, we get Cost = (2w)l + w l αβ + αγ w l -(1w)γ = (2w)l + w l α(β + γ)γ(1w) ≤ (2w)l + w l α(lα) ≤ (2w)l + wl If αγ w l -(1w)γ < 0 andβγ w l -(1w)γ < 0, we get Cost

In particular, such independent sets may include path crossing opposite arcs, the graph being directed.

2) Maximal independent sets obtained by combining these shapes

3) Non-maximal independent sets

Setting w

The independent sets covering E i and F i doublons impose the two following constraints on w.

These constraints and α

4 , which gives w 1 + l-β 4l ≤ w 1 + 1 4 ≤ 1. Therefore, setting w to 4 5 is always a valid solution.

B.3 Cost of a 4 5 -balanced coloring

Using the quantities of independent sets given in the tables above (uniformly divided between all possible instantiation of each independent set), all the doublons and half-doublons are covered with the relevant weight. This gives a complete w-balanced coloring of the star. The cost of this coloring is the total quantity of independent sets that have been used.

• The cost of the maximal independent sets of table 1) is

• The cost of the combination of independent sets in table 2) is

• The cost of the non-maximal independent sets of table 3) is

• Therefore, using max{a, a + b} = a + max{0, b} with a = 2(1w)γ, the total cost is


Adrien Socié

Yann Monerie

Frédéric Perales

Anna Pandolfi

Review of łEffects of the microstructural uncertainties on the poroelastic and the diffusive properties of mortarž

Reviewer Overall, I like this paper. The careful estimation and propagation of uncertainties, and focusing on mortar with the ITZ phase, is quite unique in my experience.

Author We agree with you but most papers in geochemistry and civil engineering use the mineral geology name [7,8,9]. The C3A clinker mineral dissolution induces the precipitation of the aluminate phase, denoted AFm in Table 1. In the validation part, the AFm phase is modeled by the monosulfoaluminate. In the application part, the AFm is represented by the katoite to apply our chemo-mechanical model [10,6]. Table 10 is modified to specify the chemical composition of the hydrate which include the katoite.

Reviewer I see in Table 1 that łanhydrate" is listed. I assume that this is the unhydrated cement phase. It should also be in Fig. 1. I see that the authors do consider it.

Author We are sorry, there was a spelling error. We talked about anhydrous or unhydrated cement or unreacted clinker. For more reliability, Figure 1 and Table 1 have been modified.

Reviewer Does Table 4 only list uncertainties? This should be clarified in the text and the caption should read łUncertainties of the material properties used as input parameters" or something like that.

Author Both Tables 4 and6 give the standard deviations parameters used in the Monte Carlo simulations.

The captions have been modified.

Reviewer I note that when the mortar uses a fixed 𝑤/𝑐 ratio = 𝑊 , that means even from the point of mixing, the 𝑤/𝑐 of the ITZ regions is < 𝑊 and the bulk paste, outside the ITZ regions, has 𝑤/𝑐 > 𝑊 . Do the authors consider this at all? I believe that this idea was considered in the authors' reference Sun et al. Would consideration of this effect change the authors' results at all? Should it?

Author In our work, the ITZ is considered from a statistical point of view. Based on the literature, the ITZ properties depend only on the matrix properties and so, the effect of the water cement ratio is not taken into account on the ITZ phase and the composition is not considered. In the validation part, the reference model [START_REF] Stora | Modelling and simulations of the chemo-mechanical behaviour of leached cement-based materials leaching process and induced loss of stiffness[END_REF]) consider the composition of the ITZ phase.

The comparison of the models show that we can capture the microstructure variation without describing the C-S-H and ITZ microstructures Reviewer 4.2.2 łThe katoite is thus the phase with the more significant impact on the efficient variation properties. ž I do not understand the English meaning of this sentence. And why would a minor phase have a major effect on uncertainties? That does not make sense to me.

Author Except for C-S-H, katoite is the hydrate inclusion admitting the greatest volume fraction uncertainty. The disparity is thus induced by the propagation of the uncertainties from the Bogue' formula [START_REF] Stutzman | Uncertainty in Bogue-calculated phase composition of hydraulic cements[END_REF] to the estimation of the cement paste composition. We have changed the sentence by: 'At cement paste scale, the variations of poroelastic properties and diffusion coefficient increase with the volume fraction uncertainties. This effect is due to two aspects.ž [...] łExcept for C-S-H, since katoite is the hydrate inclusion admitting the greatest volume fraction uncertainty, the effective properties for this phase admit a greater disparity. ž

Reviewer 2 (Anonymous)

Reviewer The authors use classical analytical schemes to upscale poroelastic and diffusive properties of cement-based materials taking into account composition variability/uncertainty and uncertainty on intrinsic phases properties. They provide a sensitivity analysis and validate their approach against experimental data. I believe that there is room for improvement in the justification of the originality of this contribution to the field.

Author Thank you for your remark. The originality of the paper is highlighted in the introduction.

Reviewer Important clarifications are needed before the study can be considered for publication.

Main concerns: On phase assemblage. The authors should specify the kind of cement system they are dealing with. Cement composition in Table 9 for example refers to OPC. Is there a reason why katoite is explicitly taken into account in the phase assemblage while other phases such as AFms are not (even if later in the paper they are mentioned in the discussion)?

Author The considered cement in the paper is Portland cement. A specification of the kind of cement system has been added in Section 2.1 łDescription of the mortar microstructurež. Concerning the katoite, the mineral is considered as a part of the AFm family phase such as monosulfoaluminate (AFms). In the validation part, the AFm phase is modeled by the monosulfoaluminate. In the application part, the AFm is represented by the katoite mineral to apply our chemo-mechanical model (Socié et al. 2021;[START_REF] Socié | Simulation of internal and external sulfate attacks of concrete with a generic reactive transport-poromechanical model[END_REF]. In Table 1, katoite is now denoted AFm for more reliability. Note that, for the validation and application, the microstructure described in Table 1 is used. The microstructure described in Table 9 is only used to estimate the standard deviations of the hydrate volume fractions (see Appendix).

Reviewer In łThe cement paste microstructure is estimated by [START_REF] Bary | Assessment of diffusive and mechanical properties of hardened cement pastes using a multi-coated sphere assemblage model[END_REF][START_REF] Tognevi | Modélisation multi-échelle et simulation du comportement thermo-hydromécanique du béton avec représentation explicite de la fissuration[END_REF]) and summarized in Table 1.ž More detail on the cement pate phase assemble adopted is needed.

Table 1 reports values that are not the same as in [START_REF] Bary | Assessment of diffusive and mechanical properties of hardened cement pastes using a multi-coated sphere assemblage model[END_REF]. Tognevi 2012 indeed shows similar values but they also report a volume fraction for AFms. Why AFms are not considered?

Author The monosulfoaluminate was only used for the validation, not for the sensitivity/uncertainties studies. The composition is taken from [START_REF] Tognevi | Modélisation multi-échelle et simulation du comportement thermo-hydromécanique du béton avec représentation explicite de la fissuration[END_REF]) that consider both katoite and AFm/AFt. Nevertheless, both works [START_REF] Bary | Assessment of diffusive and mechanical properties of hardened cement pastes using a multi-coated sphere assemblage model[END_REF] and [START_REF] Tognevi | Modélisation multi-échelle et simulation du comportement thermo-hydromécanique du béton avec représentation explicite de la fissuration[END_REF]) consider the two families of C-S-H while our study only one. So, to obtain the global C-S-H volume fraction, we added both C-S-H families. The caption of Table 1 has been changed and, to clarify these points, several comments have been added in the manuscript.

Reviewer On microstructure representation. łThe inclusions correspond to the main solid hydrated phases [START_REF] Socié | Simulation of internal and external sulfate attacks of concrete with a generic reactive transport-poromechanical model[END_REF]Socié et al. 2021): portlandite, ettringite, and katoite. ž Cement particles should also be mentioned as inclusions except if a degree of hydration (DOH) of 1 is adopted (in this case, some reserves should be added to the manuscript since for most of the realistic applications the DOH even after several years does not reach 1). Table 1 mentions anhydrates but later I read on page 13: łunder the assumption of a totally hydrated reaction". Please correct the inconsistency.

Author This article focuses on the uncertainties related to the material properties and the microstructure.

The impact of the hydration model is out of scope. The microstructure is thus based on the works of [START_REF] Bary | Assessment of diffusive and mechanical properties of hardened cement pastes using a multi-coated sphere assemblage model[END_REF]. As depicted in the article and previously described in our answers, the microstructure description is slightly modified and concern one C-S-H phase and katoite instead of monosulfoaluminate. To study the impact of the Bogue uncertainties given by [START_REF] Stutzman | Uncertainty in Bogue-calculated phase composition of hydraulic cements[END_REF], the hydration model detailed in [START_REF] Socié | Simulation of internal and external sulfate attacks of concrete with a generic reactive transport-poromechanical model[END_REF] Reviewer Capillary porosity also should be mentioned as one of the inclusions.

Author You are fully right. This has been added in Section 2.1.

Reviewer łGeneral Self-Consistent scheme is used in order to take into account a percolation of the ITZ phase". GSCS always percolates: by definition the last (𝑛 + 1)-coat functions as matrix (not to be confused with the Self-Consistent scheme for which a mechanical percolation appears at 50% of solids, and for conductivity-like properties, as it is the case of diffusion, at 33.3% of solids). The idea of using GSCS is to account for the influence of ITZ as an interphase coating the aggregate particle.

Author Thank you for your correction. The remark is taken into account in the revised version of the paper.

Reviewer Other comments: Introduction. Please rephrase for clarity the sentence: łThe material properties of mature concrete based on multiscale models are performed in two steps: first, the morphological properties are estimated, second a micromechanics model is developed". What are łmorphological properties"? Maybe mention instead that łfirst, a representation of the microstructure is adopted (regarding phases' assemblage, morphology and intrinsic properties), then a micromechanics model is deployed"

Author Thank you for your remark. The morphological properties are the volume fraction and the spatial distribution of the inclusions. The morphological descriptors refer to statistical tools used to describe mathematically the microstructure. We have changed the sentence by: łThe material properties of mature concrete based on multiscale models are performed into two steps: first, the microstructure properties such as volume fraction of inclusions or phases' assemblage are estimated, then, a micromechanics model is employed".

2021; [START_REF] Socié | Simulation of internal and external sulfate attacks of concrete with a generic reactive transport-poromechanical model[END_REF][START_REF] Socié | Modélisation chimiomécanique de la fissuration de matériaux cimentaires : vieillissement et tenue des enceintes de confinement des centrales nucléaires[END_REF]. Considering the global effect of the hydrated mineral in the transport processes remains a challenge. In the reactive transport community, some recent works extended the reactive transport model in order to capture the effect of the hydrated mineral (such as the AF) on the water content [START_REF] Ahusborde | Numerical modeling and simulation of fully coupled processes of reactive multiphase flow in porous media[END_REF][START_REF] Seigneur | Recoupling flow and chemistry in variably saturated reactive transport modelling An algorithm to accurately couple the feedback of chemistry on water consumption, variable porosity and flow[END_REF][START_REF] Socié | Benchmark simulation of CO2 injection into a reactive porous medium with a compositional flow and reactive transport simulator MIN3P. Advances in the SImulation of reactive flow and TRAnsport in porous Media[END_REF]. In these models, water is modeled as a chemical species and the ions transport lead to the dissolution/precipitation of the hydrated mineral that release/consume water that affects the flow velocity and the water content. These approaches are in accordance with our chemo-mechanical model and we prefer not to mention the proposed paper that does not consider the coupled effect of flow, ions transport, and geochemical reactions.

Reviewer Table 2 andSection Author Thank you for the articles. The parameter was already taking off a wide variety of numerical and experimental datas where the value is described in Table 12. We have added the work of [START_REF] Korb | Microstructure and texture of hydrated cement-based materials: A proton field cycling relaxometry approach[END_REF]. Taking into acccount these new datas, the mean and standard deviation are The mean and standard deviation are impacted 4.64 ± 2.84 × 10 -12 m 2 s -1 instead of 3.9 ± 2 × 10 -12 m 2 s -1 . In that way, we change all the results associate to the diffusion coefficient. [START_REF] Li | Dynamic behavior of hydration water in calcium-silicate-hydrate gel: a quasielastic neutron scattering spectroscopy investigation[END_REF]) and [START_REF] Fratini | Hydration Water Dynamics in Tricalcium Silicate Pastes by Time-Resolved Incoherent Elastic Neutron Scattering[END_REF]) respectively measured a diffusion coefficient around of 2 × 10 -9 and [1, 10] × 10 -10 . But, these values are well greater than the mean value found in the literature and the experimental results have a wide variation. Considering these values increase the mean and standard deviation parameter of the normal distribution (7.55 ± 7.136 × 10 -12 m 2 s -1 ) that does not allow the model validation (section 3.2) and they induces a variation too significant for studying the uncertainties. So, we prefer no to consider these data. Please note there was a typing error in the document for the normal distribution parameter associated with the diffusion coefficient.

Reviewer Section 4. The Monte Carlo approach for uncertainty quantification adopted with 10000 samples following a log-normal distribution is the same as in Honorio et al. łElectrical properties of cement-based materials: Multiscale modeling and quantification of the variability" CBM 2020. Since upscaling diffusivity is mathematically analogous to the conductivity problem (thermal or electrical), this reference corroborate the strategy adopted.

Author Thank you. The article has been added to the bibliography.

Reviewer Please make clear in the caption of Table 6 that the values refer to standard deviations.

Author The captions of Table 6 and Table 4 have been changed.

Reviewer Check the author's name in the reference to łHaecker".

Author There is a mistake, thank you.

Reviewer In łNote that the uncertainties could be more important for the monosulfoaluminate phases because the strength is greater than that of the katoite phase". Young modulus should be mentioned instead of strength.

;

  [START_REF] Socié | Modélisation chimiomécanique de la fissuration de matériaux cimentaires : vieillissement et tenue des enceintes de confinement des centrales nucléaires[END_REF]) is considered. As the reactive transport community[START_REF] De Windt | Modeling the degradation of Portland cement pastes by biogenic organic acids[END_REF][START_REF] Planel | Les effets couplés de la précipitation d'espèces secondaires sur le comportement mécanique et la dégradation chimique des bétons[END_REF][START_REF] Lalan | Influence d'une température de 70 • C sur la géochimie, la microstructure et la diffusion aux interfaces béton/argile : expérimentations en laboratoire[END_REF][START_REF] Seigneur | Predicting the atmospheric carbonation of cementitious materials using fully coupled two-phase reactive transport modelling[END_REF], the cement paste composition is estimated by a thermodynamic chemical solver and it is assumed a totally hydrated cement. The study leads only to obtain the standard deviation associated with the microstructure. We have modified the manuscript and Figure1to include the unhydrated cement.

  Note that in the Haecker et al. paper they adopt CH values for monosulfoaluminate elastic properties. More recent studies using molecular simulation shows that the properties of mnosulfoluminate are closer to ettringite's than CH's: H. Manzano, Atomistic Simulation Studies of the Cement Paste Components, Ph.D. thesis Universidad del Paìs Vasco, 2009. S. Hajilar, B. Shafei, Nano-scale investigation of elastic properties of hydrated cement paste constituents using molecular dynamics simulations, Comput. Mater. Sci., 2015 Honorio et al. Molecular simulation of the structure and elastic properties of ettringite and monosulfoaluminate. CCR 2020.

Author Thank you for noticing this spelling error that made the text confusing. We considered the unhydrated cement as an inclusion called łanydhrate" in Table 1. The validation and the applications rest on the microstructure of [1,2,3], which use the hydration model of Tennis and Jenning [4]. Figure 1 has been modified to include the unhydrated cement phase. Please note that another hydration model is considered in Appendix A.1 assuming a totally hydrated cement [5,6].

The differences are described in the Appendix.

Reviewer I guess katoite is the aluminate phase, from the C3A clinker mineral. I think it is better to use chemical names rather than mineral names.

Author The multiscale model is applied to reactive transport simulation or chemo-mechanical model, where the transport of ions is driven by diffusion processes and chemical reactions (Socié et al.

Author Thank you. We have updated the document to consider your remark and the article [START_REF] Honorio | Molecular simulation of the structure and elastic properties of ettringite and monosulfoaluminate[END_REF]) has been added. The article [START_REF] Hajilar | Nano-scale investigation of elastic properties of hydrated cement paste constituents using molecular dynamics simulations[END_REF] has not been added because the authors don't consider monosulfoaluminate.

Reviewer I do not believe that the following sentence adds something interesting/useful to the conclusion łFinally, at cement paste, contrary to the self-consistent scheme, the Mori-Tanaka scheme does not consider directly the volume fraction of the matrix phases. "

Author We agree with you and the manuscript has been modified.

Editor's assessment (Anna Pandolfi)

The revision of this paper has been smooth. The research was valuable and submitted to two expert reviewers, who provided an accurate review of the manuscript. Both reviewers asked for minor revisions. One of the two reviewers suggested a consistent number of new entries for the references, which perhaps were not really necessary, but authors considered all the suggestions one by one and evaluated the opportunity to add them. Even though the requested changes where minor, the revised paper has been sent to both reviewers. Only one of them returned his comments, while the editor in charge checked the conformity of the revised manuscript to the comments of the second reviewer. My opinion is that in the second revision the manuscript has been improved; it represents a good contribution to the JTCAM.


Kevin J M Martin

A circuit that combines comparison and storage in a single device

myLogoT

Registers Definition

Register: an array of D flip-flops that can hold a multibit datum, such as a byte or word

D 0 D 1 D n-1 Q 0 Q 1 Q n-1 Q 0 Q 1 Q n-1

Timing constraints

Setup and hold-time constraints to ensure that the correct data is written into the register file

The write port for a register file is implemented with a decoder that is used with the write signal to generate the C input to the registers Unit multiples of the octet (byte) may be formed with SI prefixes and binary prefixes (power of 2 prefixes) as standardized in 1998 [START_REF]Octet (computing[END_REF] 1 Byte = 8 bits 1 kilobyte (kB) = 10 3 bytes = 1 000 bytes 1 kibibyte (KiB)= 2 10 bytes = 1 024 bytes . . . Source: [START_REF] Carl | Computer Organization and Embedded Systems[END_REF] SRAM: Static Random Access Memory

Comparison of decimal and binary units

Volatile memory

Need to store software and data and not loose information when power is shut down

Caches

The illusion of a large memory accessible as fast as a small memory [11] A processor does not need to access all of the program codes and data at once. Let's keep near the useful parts. The lower portion of the address is used to select a cache entry consisting of a data word and a tag [11] myLogoT Caches

Idea

Principle of locality

Virtual address

Physical address

Translation

Mapping from a virtual to a physical address. The page size is 2 12 = 4 KiB. The number of physical pages allowed in memory is 2 28 , since the physical page number has 28 bits in it. Thus, main memory can have at most 1 TiB, while the virtual address space is 256 TiB [11] myLogoT Virtual memory The page table is indexed with the virtual page number to obtain the corresponding portion of the physical address [11] myLogoT

Virtual memory

Making the translation fast Definition TLB: translation-lookaside buffer. A cache that keeps track of recently used address mappings to try to avoid an access to the page table

1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1

Physical page address

Valid Dirty Ref

TLB

Tag

The TLB acts as a cache of the page table for the entries that map to physical pages only [11] myLogoT

Virtual memory

Making the translation fast

Physical page address

Valid Dirty Ref

TLB

Tag

The TLB acts as a cache of the page table for the entries that map to physical pages only [11] TLB

  Implementation of two read ports for a register file with n registers with a pair of n-to-1 multiplexors, each w bits wide

1 The word line is activated to close switches T 1 and T 2 2Still

 12 Two inverters cross-connected to form a latch Two bit lines (T1 and T2) b and b' are always complements myLogoT SRAM Reading and writing an SRAM cell Read Operation The Sense/Write circuit at the end of the two bit lines monitors their state Write Operation 1 The word line is activated to close switches T 1 and T 2 myLogoT Overview of memory technologies CMOS implementation of 6T SRAM memory cell [5] CMOS SRAM cell Transistor pairs (T 3 , T 5 ) and (T 4 , T 6 ) form the inverters in the latch Continuous power is needed for the cell to retain its state Content lost when power down Back in stable state when power on (but maybe not the same state) SRAMs are volatile memory because their loose their content when power is shut down Dynamic Random Access Memory A capacitor C A transistor T Why is it called Dynamic? The capacitor can retain its state for tens of milliseconds only. Need to refresh periodically. DRAMs are volatile memory because their loose their content when power is shut down Volatile memory myLogoT Overview of memory technologies DRAM physical design Source: [7] DRAM's capacity has been one of the more consistent incarnations of Moore's law [7] scaled in capacity by a factor of over 16 million 1 kbits on a die in 1970 to 16 Gbits in 2020 Did you know? myLogoT DRAM SDRAM SDRAM: Synchronous DRAM Synchronisation with a clock signal built-in refresh circuitry (hides the dynamic feature of DRAM to the user) burst mode: starting address + burst length Definition Page: a large block of data Fast Page Mode Transfer a page of data: all bytes of the selected row in sequential order no need to reselect the row successive CAS signals myLogoT DRAM DDR: Double-Data-Rate SDRAM Transfer data on both rising and falling edge of the clock Open standard Rambus Memory Differential-signaling technique to transfer data to and from the memory chips Proprietary scheme that must be licensed myLogoT DRAM Memory controller In charge of: 2 steps access: row + column, RAS + CAS signals chip select: when multiple memory modules refresh: periodic read cycles of asynchronous DRAMRefresh overheadWhen internal refresh operation occurs, the memory cannot respond Typically few percent of the total time available for accessing the memory

  Cache of 4096 blocks, four-word block size, 64-bit address 16 bytes per block ⇒ 64-4=60 bits for index and tag Direct-map cache number of sets = number of blocks ⇒ 12 bits of index (log 2 (4096) = 12) (60 -12) × 4096 = 192 Ki tag bits Two way associative cache number of sets = 2048 ⇒ 11 bits of index (log 2 (2048) = 11) (60 -11) × 2 × 2048 = 196 Ki tag bits Fully associative cache number of sets = 1 ⇒ 0 bits of index (log 2 (1) = 0) 60 × 1 × 4096 = 240 Ki tag bitsIncreasing associativity requires more comparators and more tag bitsThe size of the cache given by the manufacturer does not include the size of tags + valid bit.Compulsory miss (or cold-start miss): A cache miss caused by the first access to a block that has never been in the cache Capacity miss: A cache miss that occurs because the cache, even with full associativity, cannot contain all the blocks needed to satisfy the request Conflict miss: A cache miss that occurs in a set-associative or direct mapped cache when multiple blocks compete for the same set and that are eliminated in a fully associative cache of the same size

	Caches Caches Virtual memory
	Tags Tags Cannot reach 0% miss Mapping
	Size of tags versus associativity
	Increasing associativity requires more comparators and more tag bits 47 46 45 44 43 15 14 13 12 11 10 9 8	3 2 1 0
	The three Cs: behavior of memory hierarchies Virtual page number	Page offset
	Size of tags versus associativity
	39 38 37	15 14 13 12 11 10 9 8	3 2 1 0
		Physical page number	Page offset
				myLogoT myLogoT myLogoT

  Placing a page and finding it againDefinitionPage Table:the table containing the virtual to physical address translations stored in memory, indexed by the virtual page number each entry in the table contains the physical page number for that virtual page

		Page table register
	4 7 4 6 4 5 4 4 4 3		1 5 1 4 1 3 1 2 1 1 1 0 9 8 Virtual address	3 2 1 0	Each program has its own page table
			Virtual page number	Page offset
	Valid	36	Physical page number	12		page table register: the start of the page
						table
	Page table
						valid bit: page present or not in memory
			28
	If 0 then page is not
	present in memory
	3 9 3 8 3 7		1 5 1 4 1 3 1 2 1 1 1 0 9 8	3 2 1 0
			Physical page number	Page offset
			Physical address

  TLB is a cache, it must have a tag fieldIf TLB miss, check the page tableContext switch: changing of the internal state of the processor to allow a different process to use the processor that includes saving the state needed to return to the currently executing process

	Virtual memory
	Context switch
	Definition
	Overhead
	clear TLB entries Inefficient when high process switch rate	Typical values:
		TLB size: 16-512 entries
	Process identifier	Block size: 1-2 page table entries Miss penalty: 10-100 clock cycles
	Concatenated to the tag	Miss rate: 0.01%-1%
	TLB hit when
		myLogoT

Kevin J. M. Martin (UBS/Lab-STICC)On-chip memories at the edge AMLE -14/06/2022

read ports + 1 write port: good trade-off Kevin J. M. Martin (UBS/Lab-STICC)On-chip memories at the edge AMLE -14/06/2022

The Sense/Write circuit drives bit lines b and b', instead of sensing their state Kevin J. M. Martin (UBS/Lab-STICC)On-chip memories at the edge AMLE -14/06/2022

Source: http://www.shmj.or.jp/innovation50/english/detail_D05E.htm Source:Digital Design: Principles and Practices, Published by Jonas Wilkerson Kevin J. M. Martin (UBS/Lab-STICC) On-chip memories at the edge AMLE -14/06/2022

To, SATA

[START_REF] Dally | Power, Programmability, and Granularity: The Challenges of ExaScale Computing[END_REF] Gb/s), 2,5" Kevin J. M. Martin (UBS/Lab-STICC)On-chip memories at the edge AMLE -14/06/2022

Computation-Outside-Memory Far (COM-F): traditional computational cores [10] H. A. D. Nguyen, J. Yu, M. A. Lebdeh, M. Taouil, S. Hamdioui, and F. Catthoor. A classification of memory-centric computing. J. Emerg. Technol. Comput. Syst., 16(2), jan 2020. Kevin J. M. Martin (UBS/Lab-STICC) On-chip memories at the edge AMLE -14/06/2022

Processing close to memoryBack to the future! Kevin J. M. Martin (UBS/Lab-STICC)On-chip memories at the edge AMLE -14/06/2022

The Memory Remains ! myLogoT

Under supervision (usually operating system)

Processor provides:

starting address the number of words in the block the direction of the transfer DMA raises an interrupt when finished In virtual memory, blocks of memory (called pages) are mapped from one set of addresses (called virtual addresses) to another set (called physical addresses) [11] Size of virtual address space A 32-bit processor can address up to 2 32 = 4Gi elements A 64-bit processor can address up to 2 64 = 16Ei (exbi) elements (> 10 18 ) The tables controlling the memory are in the memory. We need to access to the memory to access to the memory!

The operating system is a process ⇒ workarounds which are making systems ever more complex more than 62% of the entire measured system energy is spent on moving data between memory and the computation units [START_REF]It's the memory, stupid[END_REF] Enabling the continued performance scaling of smaller systems requires significant research breakthroughs in three key areas [


Corine Bas

Marie Crouillere

Florence Dubelley

Marian Chatenet

Laetitia Dubau

Y Bultel

Sahal Touhami

Olivier Lottin

Assma El Kaddouri

Julia Mainka

 Dégradation

Reinforced PerfluoroSulfonic Acid membrane degradation in defective anode PEMFC

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.



  Dégradation de la membrane perfluorée renforcée en présence d'un défaut de la couche anodique dans une pile à combustible PEMFC C. Bas, M. Crouillère, F. Dubelley, M. Chatenet, L. Dubau, Y. Bultel S. Touhami, O. Lottin, A. El-Kaddouri, J. Mainka, J. Dillet O. Chadebec, G. Cauffet C. Nayoze-Coynel, F. Micoud, S. Rosini Projet ANR-CE05-2017-Locali Plénières de Fédération de recherche Hydrogène, Aussois, 31 mai 2022  Défaut dans les couches catalytiques à l'origine de la faible durabilité des piles * o Cross-over des gaz (H 2 /O 2 ) o Formation radicaux peroxyde o Amincissement localisée de la membrane **  Objectif du projet : Etude de la dégradation de la membrane (et de la propagation) induite par un manque de couche anodique Manque



  Microscopie IR -ATR Germanium Réalisation de mapping  Résolution : 1,56 µm  Chaque pixel = un spectre IR  Cartographie en absorbance pour un nb d'onde donné Membrane Tri-couche Cartographie Abs. Nb d'onde donné 11  Microscopie Raman Réalisation de pointés  Résolution : 1 µm  Spectre en nombre d'onde  Pas de spectre PFSA-C car présence Pt Limite de résolution spatiale pour couches externes  Etude zone centrale PFSA-PTFE Peu de diminution d'épaisseur dans la zone centrale  Diminution des signaux associés aux chaînes latérales • Dégradation chaine latérale ? • Perte PFSA ? Spectre RMN Microscopie Infrarouge Mise en relation des données IEC localisée, IEC globale, épaisseur des couches => Non consistant avec dégradation de la chaine latérale Défaut de couche catalytique anodique:  Dégradation PFSA • Phénomène d'Unzipping o Couches externes très dégradées (estimée entre 60 et 80 %) o Couche centrale moins dégradée (estimée entre 30 et 40 %) Conclusions | Générales Défaut de couche catalytique anodique:  Diminution épaisseur membrane : phénomène localisé • Entrée H 2 : localisé dans canaux • Sortie H 2 : plus diffus dans canaux et dents • Phénomène de propagation observé  Dégradation PFSA • Phénomène d'Unzipping o Couches externes très dégradées o Couche centrale moins dégradée (taux /2) 19 Dégradation localisée  faible diminution de l'IEC global par RMN 19 F

Remerciement : Marie-Eva Gallacio, stagiaire de DUT SGM