Generalized diversity coding is a promising proactive recovery scheme against single edge failures for unicast connections in transport networks. At the source node, the user data is split into two parts, and their bitwise XOR is computed as a third redundancy sub-flow. In order to guarantee instantaneous failure recovery without costly node upgrades, the network must ensure that any two of the three sub-flows reach the destination node in case of a single edge failure only by allowing flow duplication or merging identical flows, and avoiding any coding operation in the core network. In this paper, we investigate the corresponding routing problem to calculate capacity-efficient routes for these sub-flows. We propose a polynomial-time algorithm for topologies without capacity constraints on the links and without capability limitations of the nodes. We show that with node limitations the presented algorithm (as well as a minimum cost disjoint path-pair) provides a 4/3-approximation for the routing problem. Furthermore, we formulate an integer linear program to provide a minimum cost solution with arbitrary constraints in general graphs and we propose a polynomial-time algorithm in directed acyclic graphs. Our simulation results suggest that with upgrading only a small set of core network nodes with flow duplication and merging capabilities most of the benefits of generalized diversity coding can be achieved.

In this article we give network coding algorithms for multi‐layered video streaming. The problem is motivated by video broadcasting in a communication network to users with varying demands. We give a polynomial time algorithm for deciding feasibility for the case of two layers, and show that the problem becomes NP‐hard if the task is to maximize the number of satisfied demands. For the case of three layers we also show NP‐hardness of the problem. Finally, we propose a heuristic for three layers and give experimental comparison with previous approaches. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(1), 51–59 2018

Survivable routing methods have been thoroughly investigated in the past decades in transport networks. However, the proposed approaches suffered either from slow recovery time, poor bandwidth utilization, high computational or operational complexity, and could not really provide an alternative to the widely deployed single edge failure resilient dedicated 1 + 1 protection approach. Diversity coding is a candidate to overcome these difficulties with a relatively simple technique: dividing the connection data into two parts, and adding some redundancy at the source node. However, a missing link to make diversity coding a real alternative to 1+1 in transport networks is finding its minimum cost survivable routing, even in sparse topologies, where previous approaches may fail. In this paper we propose a polynomial-time algorithm with O(|V||E| log |V|) complexity for this routing problem. On the other hand, we show that the same routing problem turns to be NP-hard as soon as we limit the forwarding capabilities of some nodes and the capacities of some links of the network.

Let ℱ be a family of pairs of sets. We call it an (a, b)-set system if for every set-pair (A,B) in ℱ we have that |A| = a, |B| = b, and A ∩ B = Ø. Furthermore, ℱ is weakly cross-intersecting if for any (Ai , Bi ), (Aj , Bj ) ∈ ℱ with i ≠ j we have th

This is the first half of a two-part paper devoted to on-line 3-colorable graphs. Here on-line 3-colorable triangle-free graphs are characterized by a finite list of forbidden induced subgraphs. The key role in our approach is played by the family of graphs which are both triangle- and (2K2 + K1)-free. Characterization of this family is given by introducing a bipartite modular decomposition concept. This decomposition, combined with the greedy algorithm, culminates in an on-line 3-coloring algorithm for this family. On the other hand, based on the characterization of this family, all 22 forbidden subgraphs of on-line 3-colorable triangle-free graphs are determined. As a corollary, we obtain the 10 forbidden subgraphs of on-line 3-colorable bipartite graphs. The forbidden subgraphs in the finite basis characterization are on-line 4-critical, i.e., they are on-line 4-chromatic but their proper induced subgraphs are on-line 3-colorable. The results of this paper are applied in the companion paper [Discrete Math., 177 (1997), pp. 99--122] to obtain the finite basis characterization of connected on-line 3-colorable graphs (with 51 4-critical subgraphs). However, perhaps surprisingly, connectivity (or the triangle-free property) is essential in a finite basis characterization: there are infinitely many on-line 4-critical graphs.