This paper aims to transform a trained classifier into an abstaining classifier, such that the latter is provably protected from out-of-distribution and adversarial samples. The proposed Sample-efficient Probabilistic Detection using Extreme Value Theory (SPADE) approach relies on a Generalized Extreme Value (GEV) model of the training distribution in the latent space of the classifier. Under mild assumptions, this GEV model allows for formally characterizing out-of-distribution and adversarial samples and rejecting them. Empirical validation of the approach is conducted on various neural architectures (ResNet, VGG, and Vision Transformer) and considers medium and large-sized datasets (CIFAR-10, CIFAR-100, and ImageNet). The results show the stability and frugality of the GEV model and demonstrate SPADE’s efficiency compared to the state-of-the-art methods.

International audience

Abstract. Given a graph [Formula: see text], a coloring of [Formula: see text] is acyclic if it is a proper coloring of [Formula: see text] and every cycle contains at least three colors. Its acyclic chromatic number [Formula: see text] is the minimum [Formula: see text] such that an acyclic [Formula: see text]-coloring of [Formula: see text] exists. When [Formula: see text] has maximum degree [Formula: see text], it is known that [Formula: see text] as [Formula: see text] and that [Formula: see text] if, in addition, [Formula: see text] does not contain [Formula: see text] as a subgraph. We study the extremal value of the acyclic chromatic number in the class of graphs of maximum degree [Formula: see text] that do not contain some fixed subgraph [Formula: see text] on [Formula: see text] vertices. We establish that this extremal value is at most [Formula: see text] if [Formula: see text] is a tree, [Formula: see text] if [Formula: see text] is bipartite and can be made acyclic with the removal of one vertex, [Formula: see text] if [Formula: see text] is an even cycle of length at least 6, and [Formula: see text] if [Formula: see text]. Moreover, we exhibit an infinite family of obstructions [Formula: see text] that each induces a different asymptotic behavior for this extremal value. This is obtained with the derivation of lower bounds that come from the analysis of the acyclic chromatic number of a random graph drawn from either [Formula: see text] or [Formula: see text], which we entirely determine up to a [Formula: see text] factor. As a byproduct, we can certify that most of our results are tight up to a [Formula: see text] factor.

We introduce a game where players selfishly choose a resource and endure a cost depending on the number of players choosing nearby resources. We model the influences among resources by a weighted graph, directed or not. These games are generalizations of well-known games like Wardrop and congestion games. We study the conditions of equilibria existence and their efficiency if they exist. We conclude with studies of games whose influences among resources can be modelled by simple graphs.

Interpretability is a desirable property for machine learning and decision models, particularly in the context of safety-critical applications. Another most desirable property of the sought model is to be unique or {\em identifiable} in the considered class of models: the fact that the same functional dependency can be represented by a number of syntactically different models adversely affects the model interpretability, and prevents the expert from easily checking their validity. This paper focuses on the Choquet integral (CI) models and their hierarchical extensions (HCI). HCIs aim to support expert decision making, by gradually aggregating preferences based on criteria; they are widely used in multi-criteria decision aiding {and are receiving interest from the} Machine Learning {community}, as they preserve the high readability of CIs while efficiently scaling up w.r.t. the number of criteria. The main contribution is to establish the identifiability property of HCI under mild conditions: two HCIs implementing the same aggregation function on the criteria space necessarily have the same hierarchical structure and aggregation parameters. The identifiability property holds even when the marginal utility functions are learned from the data. This makes the class of HCI models a most appropriate choice in domains where the model interpretability and reliability are of primary concern.

Multi-Criteria Decision Making (MCDM) aims at modelling expert preferences and assisting decision makers in identifying options best accommodating expert criteria. An instance of MCDM model, the Choquet integral is widely used in real-world applications, due to its ability to capture interactions between criteria while retaining interpretability. Aimed at a better scalability and modularity, hierarchical Choquet integrals involve intermediate aggregations of the interacting criteria, at the cost of a more complex elicitation. The paper presents a machine learning-based approach for the automatic identification of hierarchical MCDM models, composed of 2-additive Choquet integral aggregators and of marginal utility functions on the raw features from data reflecting expert preferences. The proposed NEUR-HCI framework relies on a specific neural architecture, enforcing by design the Choquet model constraints and supporting its end-to-end training. The empirical validation of NEUR-HCI on real-world and artificial benchmarks demonstrates the merits of the approach compared to state-of-art baselines.

In a network, a tunnel is a part of a path where a protocol is encapsulated in another one. A tunnel starts with an encapsulation and ends with the corresponding decapsulation. Several tunnels can be nested at some stage, forming a protocol stack. Tunneling is very important nowadays and it is involved in several tasks: IPv4/IPv6 transition, VPNs, security (IPsec, onion routing), etc. However, tunnel establishment is mainly performed manually or by script, which present obvious scalability issues. Some works attempt to automate a part of the process (e.g., TSP, ISATAP, etc.). However, the determination of the tunnel(s) endpoints is not fully automated, especially in the case of an arbitrary number of nested tunnels. The lack of routing protocols performing automatic tunneling is due to the unavailability of path computation algorithms taking into account encapsulations and decapsulations. There is a polynomial centralized algorithm to perform the task. However, to the best of our knowledge, no fully distributed path computation algorithm is known. Here, we propose the first fully distributed algorithm for path computation with automatic tunneling, i.e., taking into account encapsulation, decapsulation and conversion of protocols. Our algorithm is a generalization of the distributed Bellman-Ford algorithm, where the distance vector is replaced by a protocol stack vector. This allows to know how to route a packet with some protocol stack. We prove that the messages size of our algorithm is polynomial, even if the shortest path can be of exponential length. We also prove that the algorithm converges after a polynomial number of steps in a synchronized setting. We adapt our algorithm into aproto-protocol for routing with automatic tunneling and we show its efficiency through simulations.

We consider a multi‐domain network scenario and we study the Inter‐Domain Path Computation problem under the Domain Uniqueness constraint ( ‐ ), that is, a path cannot visit a domain twice. It is known that hierarchical Path Computation Element (h‐PCE) architecture, that is commonly used to solve ‐ , shows poor scalability with respect to the number of domains. For this reason, we devise a new domain clustering concept allowing one to artificially reduce the number of domains in an offline phase, in order to solve ‐ with lower complexity at run‐time. More specifically, we first prove the ‐completeness of the feasibility problem associated with ‐ and the inapproximability of ‐ itself. Yet, we show that the number of domains is the real computational bottleneck for the solution of ‐ . Then we provide a necessary and sufficient condition for a domain clustering to be proper, that is, without loss of optimality. Such a condition can be verified offline on the inter‐domain graph. We finally show via numerical experiments the impact of the inter‐domain treewidth on the computational speed‐up brought by proper clustering.

Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to a suboptimal use of the network resources and to additional operational costs. However, some routers are able to encapsulate, decapsulate, and convert protocols, and act as a liaison between these layers. A unified control plane would be useful to optimize the use of the network resources and to automate the routing configurations. Software-defined networking-based architectures offer an opportunity to design such a control plane. One of the most important problems to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem, as they do not take into account encapsulations and conversions of protocols. In this paper, we propose algorithms to solve this problem and study several cases. If there is no bandwidth constraint, we propose a polynomial algorithm that computes the optimal path. We also give lower and upper bounds on the optimal path length. On the other hand, we show that the problem is NP-hard if there is a bandwidth constraint (or other quality-of-service parameters), even if there is only two protocols and in a symmetric graph. We study the complexity and the scalability of our algorithms and evaluate their performances on real and random topologies. The results show that they are faster than the previous ones proposed in the literature. These algorithms can also have important applications in automatic tunneling.

We address online scheduling for servers of Cloud service providers. Each server is composed of several variable-speed processors whose power function is convex. The servers may be busy, idle or switched off. The objective of our scheduling is to minimize the energy consumed by a Cloud computing platform. To achieve this goal, we try to anticipate computing demands by predicting a workload, then we modify the set of available servers to fit this prediction and finally we schedule our jobs on the available servers. To schedule jobs we have developed the POD (Predict Optimize Dispatch) algorithm. We evaluate its performance for real-life traces in the presence of different types of prediction. The analysis shows that our scheduling reduces energy consumption considerably.

This paper examines the equilibrium convergence properties of no-regret learning with exponential weights in potential games. To establish convergence with minimal information requirements on the players' side, we focus on two frameworks: the semi-bandit case (where players have access to a noisy estimate of their payoff vectors, including strategies they did not play), and the bandit case (where players are only able to observe their in-game, realized payoffs). In the semi-bandit case, we show that the induced sequence of play converges almost surely to a Nash equilibrium at a quasi-exponential rate. In the bandit case, the same result holds for approximate Nash equilibria if we introduce a constant exploration factor that guarantees that action choice probabilities never become arbitrarily small. In particular, if the algorithm is run with a suitably decreasing exploration factor, the sequence of play converges to a bona fide Nash equilibrium with probability 1.

MOTIVATION: Predicting the 3D structure of RNA molecules is a key feature towards predicting their functions. Methods which work at atomic or nucleotide level are not suitable for large molecules. In these cases, coarse-grained prediction methods aim to predict a shape which could be refined later by using more precise methods on smaller parts of the molecule. RESULTS: We developed a complete method for sampling 3D RNA structure at a coarse-grained model, taking a secondary structure as input. One of the novelties of our method is that a second step extracts two best possible structures close to the native, from a set of possible structures. Although our method benefits from the first version of GARN, some of the main features on GARN2 are very different. GARN2 is much faster than the previous version and than the well-known methods of the state-of-art. Our experiments show that GARN2 can also provide better structures than the other state-of-the-art methods. AVAILABILITY AND IMPLEMENTATION: GARN2 is written in Java. It is freely distributed and available at http://garn.lri.fr/. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to a suboptimal use of the network resources and additional operational costs. However, some routers are able to encapsulate, decapsulate and convert protocols and act as a liaison between these layers. A unified control plane would be useful to optimize the use of the network resources and automate the routing configurations. Software-Defined Networking (SDN) based architectures, such as OpenFlow, offer a chance to design such a control plane. One of the most important problems to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem as they do not take into account encapsulations and conversions of protocols. In this paper, we propose algorithms to solve this problem and study several cases: Path computation without bandwidth constraint, under bandwidth constraint and under other Quality of Service constraints. We study the complexity and the scalability of our algorithms and evaluate their performances on real topologies. The results show that they outperform the previous ones proposed in the literature.

We present the first polynomial self-stabilizing algorithm for finding a (2/3)-approximation of a maximum matching in a general graph. The previous best known algorithm has been presented by Manne et al. and has a sub-exponential time complexity under the distributed adversarial daemon. Our new algorithm is an adaptation of the Manne et al. algorithm and works under the same daemon, but with a time complexity in O(n^3) moves. Moreover, our algorithm only needs one more boolean variable than the previous one, thus as in the Manne et al. algorithm, it only requires a constant amount of memory space (three identifiers and two booleans per node).

In order to achieve high data rates in future wireless packet switched cellular networks, aggressive frequency reuse is inevitable due to the scarcity of the radio resources. While intra-cell interference is mostly mitigated and can be ignored, inter-cell interference can severely degrade performances of end-users. Hence, Inter-Cell Interference Coordination is commonly identified as a key radio resource management mechanism to enhance system performance of 4G networks. This paper addresses the problem of ICIC in the downlink of Long Term Evolution (LTE) systems where the Resource Blocks (RB) selection process is inspired from the reinforcement learning theory targeted to address the adversarial Multi-Armed Bandit problem. We resort to the popular EXP3 algorithm whose goal is to steer autonomously the decision of each Base Station (BS) towards the least interfered RBs while ensuring reactivity to the possible changes that can occur in the common resource usage and radio channel quality. However, the EXP3 algorithm is computationally heavy as its strategy set grows exponentially with the number of needed RBs and the total amount of available RBs. Therefore, we propose an efficient adaptation of the EXP3 algorithm, deemed Q-EXP3, where the needed RBs are selected one by one requiring only polynomial time computation.

Summary On resource sharing platforms, the execution of the jobs submitted by users is usually controlled by a centralized global scheduler. It determines efficient schedules regarding some common objective function that all organizations agree with (for instance, maximizing the utilization of the entire platform). However, in practice, each organization is mostly interested in the performance obtained for its own jobs. We study the price that the collectivity must pay in order to allow independence to selfish, self‐governing organizations, so they can choose the best schedules for their own jobs. In other words, we are interested in analyzing the costs on the global performance inflicted by the decentralization of scheduling policies. We present a game‐theoretic model for the problem and the associated coordination mechanisms developed to reduce the cost of the decentralization of the decision‐making process. The main contribution is to show (in theory and practice) how to devise pure Nash equilibria configurations for every instance of the problem and to prove that the price paid by the collectivity depends on the local scheduling policy and on the characteristics of the workload executed on such platforms. Copyright © 2014 John Wiley & Sons, Ltd.

In order to achieve high data rates in future wireless packet switched cellular networks, aggressive frequency reuse is inevitable due to the scarcity of the radio resources. While intra-cell interference is mostly mitigated and can be ignored, inter-cell interference can severely degrade performances with bad channel quality. Hence, Inter-Cell Interference Coordination (ICIC) is commonly identified as a key radio resource management mechanism to enhance system performance of 4G networks. This paper addresses the problem of ICIC in the downlink of Long Term Evolution (LTE) systems where the resource selection process is apprehended as a potential game. Proving the existence of Nash Equilibriums (NE) shows that stable resource allocations can be reached by selfish Base Stations (BS). We put forward a fully decentralized algorithm based on replicator dynamics to attain the pure NEs of the modeled game. Each BS will endeavor to select a set of favorable resources with low interference based on local knowledge only making use of signaling messages already present in the downlink of LTE systems.

Inter-Cell Interference Coordination (ICIC) is commonly identified as a key radio resource management mechanism to enhance system performance of 4G networks. This paper addresses the problem of ICIC in the downlink of cellular OFDMA systems where the power level selection process of resource blocks (RB) is apprehended as a sub-modular game. The existence of Nash equilibriums (NE) for that type of games shows that stable power allocations can be reached by selfish Base Stations (BS). We put forward a semi distributed algorithm based on best response dynamics to attain the NEs of the modeled game. Based on local knowledge conveyed by the X2 interface in LTE (Long Term Evolution) networks [1], each BS will first select a pool of favorable RBs with low interference. Second, each BS will strive to fix the power level adequately on those selected RBs realizing performances comparable with the Max Power policy that uses full power on selected RBs while achieving substantial power economy. Finally, we compare the obtained results to an optimal global solution to quantify the efficiency loss of the distributed game approach. It turns out that even though the distributed game results are sub-optimal, the low degree of system complexity and the inherent adaptability make the decentralized approach promising especially for dynamic scenarios.

Inter-Cell Interference Coordination (ICIC) is commonly identified as a key radio resource management mechanism to enhance system performance of 4G networks. This paper addresses the problem of ICIC in the downlink of cellular OFDMA systems where the resource selection process is apprehended as a congestion game. Proving the existence of Pure Nash equilibriums (PNE) shows that stable resource allocations can be reached by selfish Base Stations (BS). We resort to a fully decentralized algorithm proposed by Berenbrinck et al [1] to attain the PNEs of the modeled game. Each BS will strive to select a pool of favorable resources with low interference based on local knowledge only.

A Service Level Agreement (SLA) is a contract between a customer and a Network Service Provider (NSP) defining services to one or more destinations at a given Quality of Service (QoS). Once committed, the SLA can be violated without the customer being able to predict that. We focus on offer selection mechanisms according to QoS and taking into account past SLAs' violations. We propose an algorithm, using a minimizing-regret technique, which provides an estimation of the reliability of given NSPs to the customer. Our approach only requires an end-to-end monitoring tool for used paths and depends on the customer's history.

Nowadays, with the abundance of IEEE 802.11 access points (APs), a mobile user has the flexibility to choose one of several APs, each using a separate channel. Rather than relying on the simplistic standardized algorithm to select the AP, it would be preferable to use optimal algorithms that reduce the user data transfer time. In this paper, the AP selection process is apprehended as an ordinal potential game, which is a class of non-cooperative games known to possess at least one pure Nash Equilibrium (PNE). We put forward a fully decentralized algorithm based on replicator dynamics to attain those PNE. Further, to assess the loss in efficiency of the proposed selfish distributed algorithm, we compare its performances against a centralized optimal approach derived by solving a mixed integer linear program.

With the abundance of diverse air interfaces in the same operating area, a mobile user is able to connect concurrently to different wireless access networks in order to meet more easily its target performance. In this paper, we consider the downlink of a multi-class hybrid network with two Radio Access Technologies (RAT): WiMAX and WiFi. We devise a distributed Radio Resource Management (RRM) scheme for elastic traffic that coexists with streaming traffic. The proposed scheduling policy is original in the sense that elastic users have a counterintuitive behaviour: they will try to occupy the least amount possible of bandwidth owing to their delay tolerance to accommodate QoS stringent streaming users. A non-cooperative submodular game is used to load balance the traffic of elastic users between the two available RATs aiming at minimizing their bandwidth consumption. We characterize the Nash Equilibriums (NE) of the resource management game and study the efficiency of a distributed algorithm based on best response dynamics to achieve those equilibriums. The game is played upon every new arrival and an admission control scheme is used to limit the number of ongoing connections so that admitted elastic flows are sustained with a guaranteed minimal rate.

Owing to the proliferation of different Radio Access Technologies (RAT) in the same operating area, a mobile user is capable of connecting concomitantly to diverse wireless networks in order to meet more easily its target performance. In this paper, we consider the downlink of a multi-class hybrid network with two RATs: WiMAX and 3G LTE. We put forward a semi-distributed Radio Resource Management (RRM) scheme for elastic traffic where both the system and mobile users intervene in the resource management policy. The proposed scheduling scheme is original in the sense that users with elastic traffic have a counterintuitive behavior: they will try to occupy the least amount possible of bandwidth to accommodate QoS stringent streaming traffic. A non-cooperative game is used to load balance the traffic of elastic users between the two available RATs aiming at minimizing their bandwidth consumption. We characterize the Nash Equilibriums (NE) of the RRM game and study the efficiency of a best response algorithm to achieve those equilibriums. Moreover, we propose a fully decentralized algorithm based on replicator dynamics to attain NEs. The system role is to apply an admission control algorithm that limits the number of ongoing connections so that elastic traffic is sustained with a guaranteed minimal rate.

We conduct a game theoretic analysis on the problem of scheduling jobs on computing platforms composed of several independent and selfish organizations, known as the Multi-Organization Scheduling Problem (MOSP). Each organization shares resources and jobs with others, expecting to decrease the makespan of its own jobs. We modeled MOSP as a non-cooperative game where each agent is responsible for assigning all jobs belonging to a particular organization to the available processors. The local scheduling of these jobs is defined by coordination mechanisms that first prioritize local jobs and then schedule the jobs from others according to some given priority. When different priorities are given individually to the jobs - like in classical scheduling algorithms such as LPT or SPT - then no pure e-approximate equilibrium is possible for values of e less than 2. We also prove that even deciding whether a given instance admits or not a pure Nash equilibrium is co-NP hard. When these priorities are given to entire organizations, we show the existence of an algorithm that always computes a pure ρ-approximate equilibrium using any ρ-approximation list scheduling algorithm. Finally, we prove that the price of anarchy of the MOSP game using this mechanism is asymptotically bounded by 2.

Nowadays, with the abundance of diverse air interfaces in the same operating area, advanced Radio Resource Management (RRM) is vital to take advantage of the available system resources. In such a scenario, a mobile user will be able to connect concurrently to different wireless access networks. In this paper, we consider the downlink of a hybrid network with two broadband Radio Access Technologies (RAT): WiMAX and WiFi. Two approaches are proposed to load balance the traffic of every user between the two available RATs: an individual approach where mobile users selfishly strive to improve their performance and a global approach where resource allocation is made in a way to satisfy all mobile users. We devise for the individual approach a fully distributed resource management scheme portrayed as a non-cooperative game. We characterize the Nash equilibriums of the proposed RRM game and put forward a decentralized algorithm based on replicator dynamics to achieve those equilibriums. In the global approach, resources are assigned by the system in order to enhance global performances. For the two approaches, we show that after convergence, each user is connected to a single RAT which avoids costly traffic splitting between available RATs.

SUMMARY In this paper we consider the problem of scheduling on computing platforms composed of several independent organizations, known as the Multi‐Organization Scheduling Problem (MOSP). Each organization provides both resources and jobs and follows its own objectives. We are interested in the best way to minimize the makespan on the entire platform when the organizations behave in a selfish way. We study the complexity of the MOSP problem with two different local objectives—makespan and average completion time—and show that MOSP is strongly NP‐Hard in both cases. We formally define a selfishness notion, by means of restrictions on the schedules. We prove that selfish behavior imposes a lower bound of 2 on the approximation ratio for the global makespan. We present various approximation algorithms of ratio 2 which validate selfishness restrictions. These algorithms are experimentally evaluated through simulation, exhibiting good average performances and presenting good fairness to organizations' local objectives. Copyright © 2011 John Wiley & Sons, Ltd.

Stabilizing distributed systems expect all the component processes to run predefined programs that are externally mandated. In Internet scale systems, this is unrealistic, since each process may have selfish interests and motives related to maximizing its own payoff. This article formulates the problem of selfish stabilization to show how competition blends with cooperation in a stabilizing environment.

We study the problem of redistributing data between clusters interconnected by a backbone. We suppose that at most k communications can be performed at the same time (the value of k depending on the characteristics of the platform). Given a set of messages, we aim at minimizing the total communication time assuming that communications can be preempted and that preemption comes with an extra cost. Our problem, called k-preemptive bipartite scheduling (KPBS) is proven to be NP-hard. We study its lower bound. We propose two 8/3-approximation algorithms with low complexity and fast heuristics. Simulation results show that both algorithms perform very well compared to the optimal solution and to the heuristics. Experimental results, based on an MPI implementation of these algorithms, show that both algorithms outperform a brute-force TCP-based solution, where no scheduling of the messages is performed

This paper is concerned with all-optical networks using deflection routing and time division multiplexing. Slotted networks make use of the synchronous arrival of the packets to the routers to minimize locally the number of deflections. We show that the difference in performance between slotted and unslotted networks is mainly due to the fact that unslotted networks cannot easily perform such local optimization. We also show that minimizing locally the number of deflections in unslotted networks gives rise to an NP-complete problem. To overcome this problem, we have designed a heuristic whose aim is to limit locally the number of deflections. We experimentally demonstrate that this heuristic enhances unslotted routing almost at the same performance level as slotted routing. As a consequence, we have shown that unslotted deflection routing can be implemented is a way which makes it a competitive alternative to slotted deflection routing for optical time division multiplexing deflection networks.

This paper is devoted to multi-point communication problems under the all-port line model.The line model assumes long distance calls between non neighboring processors.In this sense, the line model is strongly related to circuit-switched networks, wormhole routing, optical networks supporting wavelength division multiplexing, ATM switching, and networks supporting connected mode routing protocols.Since tree-networks are basic tools for t,he management of multi-point applications in both parallel systems and computer networks, we propose polynomial algorithms to derive optimal or near optimal broadcast, multicast and gossip protocols in trees. 'Additional support

This paper addresses the one-to-all broadcasting problem and the one-to-many broadcasting problem, usually simply called broadcasting and multicasting, respectively. Broadcasting is the information dissemination problem in which a node of a network sends the same piece of information to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both operations have many applications in parallel and distributed computing. In this paper, we study these problems in both line model, and cut-through model. The former assumes long distance calls between nonneighboring processors. The latter strengthens the line model by taking into account the use of a routing function. Long distance calls are possible in circuit-switched and wormhole-routed networks, and also in many networks supporting optical facilities. In the line model, it is well known that one can compute in polynomial time a [log/sub 2/n]-round broadcast or multicast protocol for any arbitrary network. Unfortunately such a protocol is often inefficient from a practical point of view because it does not use the resources of the network in a balanced way. In this paper, we present a new algorithm to compute broadcast or multicast protocols. This algorithm applies under both line and cut-through models. Moreover, it returns protocols that efficiently use the bandwidth of the network. From a complexity point of view, we also show that most of the optimization problems relative to the maximization of the efficiency of broadcast or multicast protocols in terms of switching time or vertex load are NP-complete. We have, however, derived polynomial efficient solutions for tree-networks.