Show simple item record

dc.contributor.authorManley, Eric D.
dc.contributor.authorGormley, John
dc.date.accessioned2014-06-02T14:38:07Z
dc.date.available2014-06-02T14:38:07Z
dc.date.issued2014-04
dc.identifier.citationProceedings of the Midwest Instruction & Computing Symposium, April 2014en_US
dc.identifier.urihttp://hdl.handle.net/2092/2062
dc.description.abstractNetwork coding, a relatively new paradigm for transmitting information through communication networks, allowing intermediate nodes in the network to combine data received on separate incoming channels before transmitting on outgoing channels. When compared with traditional routing paradigms, network coding can result in benefits such as higher throughput, fault-tolerance, and security. In this paper, we focus on studying network coding properties on a specific class of graphs called grid graphs. Network coding properties are related to well-known Steiner properties in graphs. Specifically, Steiner properties of grid graphs are studied, because they model VLSI layout design, which makes network coding properties a natural extension of this investigation. In particular, we looked at the maximum size of a communication group that is possible in a grid graph, given a specific desired transmission rate. Letting rk (G) be the maximum fraction of nodes in graph G that can be included in a network coded multicast group with an integral flow of size k, we prove that r2(G)<1, r3(G) < 1 2 , and r4(G) < 1 3 . In the first two cases, we construct families of communication groups on grid graphs which approach these bounds. In the latter case, we present a family of communication groups approaching a density of 14 .en_US
dc.language.isoen_USen_US
dc.publisherMICSen_US
dc.subjectNetwork codingen_US
dc.subjectGraph theoryen_US
dc.subjectGrid graphsen_US
dc.subjectMulticasten_US
dc.titleMulticast Network Coded Flow In Grid Graphsen_US
dc.typeArticleen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record