Precoding-Based Network Alignment Using Transform Approach for Acyclic Networks With Delay

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a F(p)m-linear combination of the input symbols across different generations, where F(p)m denotes the field over which the network operates (p is prime and m is a positive integer). We use finite-field discrete Fourier transform to convert the output symbols at the sink nodes, at any given time instant, into a F(p)m-linear combination of the input symbols generated during the same generation without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach. When the zero-interference conditions are not satisfied, we propose three precoding-based network alignment (PBNA) schemes for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D) termed as PBNA using transform approach and time-invariant local encoding coefficients (LECs), PBNA using time-varying LECs, and PBNA using transform approach and block time-varying LECs. We derive sets of necessary and sufficient conditions under which throughputs close to n' + 1/2n' + 1, n'/2n' + 1, and n'/2n' + 1 are achieved for the three source-destination pairs in a 3-S 3-D MUN-D employing PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs, where n' is a positive integer. For PBNA using time-varying LECs, we obtain a sufficient condition under which a throughput demand of n(1)/n, n(2)/n, and n(3)/n can be met for the three source-destination pairs in a 3-S 3-D MUN-D, where n(1), n(2), and n(3) are positive integers less than or equal to the positive integer n. This condition is also necessary when n(1) + n(3) = n(1) + n(2) = n where n(1) >= n(2) >= n(3).

Space-Time Coded Spatial Modulated Physical Layer Network Coding for Two-Way Relaying

Using the spatial modulation approach, where only one transmit antenna is active at a time, we propose two transmission schemes for two-way relay channel using physical layer network coding with space time coding using coordinate interleaved orthogonal designs (CIODs). It is shown that using two uncorrelated transmit antennas at the nodes, but using only one RF transmit chain and space-time coding across these antennas can give a better performance without using any extra resources and without increasing the hardware implementation cost and complexity. In the first transmission scheme, two antennas are used only at the relay, adaptive network coding (ANC) is employed at the relay and the relay transmits a CIOD space time block code (STBC). This gives a better performance compared to an existing ANC scheme for two-way relay channel which uses one antenna each at all the three nodes. It is shown that for this scheme at high SNR the average end-to-end symbol error probability (SEP) is upper bounded by twice the SEP of a point-to-point fading channel. In the second transmission scheme, two transmit antennas are used at all the three nodes, CIOD STBCs are transmitted in multiple access and broadcast phases. This scheme provides a diversity order of two for the average end-to-end SEP with an increased decoding complexity of O(M-3) for an arbitrary signal set and O(M-2 root M) for square QAM signal set. Simulation results show that the proposed schemes performs better than the existing ANC schemes under perfect and imperfect channel state information.

Experimental studies on the influence of intermediate principal stress and inclination on the mechanical behaviour of angular sands

A comprehensive experimental study has been made on angular sand to investigate various aspects of mechanical behavior. A hollow cylinder torsion testing apparatus is used in this program to apply a range of stress conditions on this angular quartzitic fine sand under monotonic drained shear. The effect of the magnitude and inclination of the principal stresses on an element of sand is studied through these experiments. This magnitude and inclination of the principal stresses are presented as an ``ensemble measure of fabric in sands''. This ensemble measure of fabric in the sands evolves through the shearing process, and reaches the final state, which indeed has a unique fabric. The sand shows significant variation in strength with changing inclination of the principal stresses. The locus of the final stress state in principal stress space is also mapped from these series of experiments. Additional aspects of non-coaxiality, a benchmarking exercise with a few constitutive models is presented here. This experimental approach albeit indirect shows that a unique state which is dependent on the fabric, density and confining stress exists. This suite of experiments provides a well-controlled data set for a clear understanding on the mechanical behavior of sands.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

On Locally Gabriel Geometric Graphs

Let be a set of points in the plane. A geometric graph on is said to be locally Gabriel if for every edge in , the Euclidean disk with the segment joining and as diameter does not contain any points of that are neighbors of or in . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any , there exists LGG with edges. This improves upon the previous best bound of . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any point set, there exists an independent set of size .

A note on tetrablock contractions

A commuting triple of operators (A, B, P) on a Hilbert space H is called a tetrablock contraction if the closure of the set E = {(a(11),a(22),detA) : A = GRAPHICS] with parallel to A parallel to <1} is a spectral set. In this paper, we construct a functional model and produce a set of complete unitary invariants for a pure tetrablock contraction. In this construction, the fundamental operators, which are the unique solutions of the operator equations A - B* P = DPX1DP and B - A* P = DPX2DP where X-1, X-2 is an element of B(D-P) play a pivotal role. As a result of the functional model, we show that every pure tetrablock isometry (A, B, P) on an abstract Hilbert space H is unitarily equivalent to the tetrablock contraction (MG1*+G2z, MG2*+G1z, M-z) on H-DP*(2). (D), where G(1) and G(2) are the fundamental operators of (A*, B*, P*). We prove a Beurling Lax Halmos type theorem for a triple of operators (MF1*+F2z, MF2*+F1z, M-z), where epsilon is a Hilbert space and F-1, F-2 is an element of B(epsilon). We also deal with a natural example of tetrablock contraction on a functions space to find out its fundamental operators.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.