Dependence Deduction: A New Perspective in Constructing Matroidal Networks
Date
2013-09-25
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Matroidal networks play a fundamental role in proving theoretical results on the limitation of network coding. This can be explained by the underlying connections between network coding and matroid theory. Two existing methods are known in the network coding literature for constructing networks from a matroid. The method due to Dougherty et al. has high time complexity but can create relatively simple network structures from a given matroid. The method due to El Rouayheb et al. has low time complexity, but results in rather complex network structures. This thesis studies the design of matroidal networks from uniform and whirl matroids, targeting both low time complexity and minimum network sizes. Our construction is based on the new technique of dependence deduction, which may serve as a promising direction for constructing general matroidal networks. Some of our constructions lead to new networks for understanding network coding in terms of base eld requirements.
Description
Keywords
Computer Science
Citation
He, M. (2013). Dependence Deduction: A New Perspective in Constructing Matroidal Networks (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/25550