Header menu link for other important links
X
Public-private separation in linear network-coded simultaneous multicast and unicast
Published in
2012
Abstract
We consider a network coding problem with a single source and multiple sinks. A common set of messages is demanded by all sinks. In addition, each sink demands a private set of messages, which is disjoint from the private set of all other sinks. This pattern of demands is called simultaneous multicast and unicast. This is a specific case of the general connections problem, for which determining the existence of a linear network coding solution is NP-hard. However, the multicast or disjoint broadcast problems, which are the individual components of the simultaneous multicast and unicast problem, are both linearly solvable in polynomial time. Observing that the mincut conditions are insufficient to show the existence of linear network coding solution for simultaneous multicast and unicast, we study a new set of sufficient conditions. We show that public-private separation is the sufficient condition for the existence of linear network coding solution. We start with a set of graphs called 3-level graphs and provide certain extensions. © 2012 IEEE.
About the journal
Journal2012 National Conference on Communications, NCC 2012
Open AccessNo
Concepts (17)
  •  related image
    3 LEVELS
  •  related image
    BROADCAST PROBLEM
  •  related image
    Individual components
  •  related image
    Min-cut
  •  related image
    MULTICASTS
  •  related image
    Np-hard
  •  related image
    Polynomial-time
  •  related image
    PUBLIC-PRIVATE
  •  related image
    Single source
  •  related image
    Sufficient conditions
  •  related image
    Unicast
  •  related image
    Unicast problems
  •  related image
    Linear networks
  •  related image
    Network coding
  •  related image
    Polynomial approximation
  •  related image
    Separation
  •  related image
    Multicasting