Back to overview page. This list as a PDF.
[1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204-1216, July 2000. [ bib ]
[2] G. Ausiello, P. G. Franciosa, and D. Frigioni. Directed hypergraphs: Problems, algorithmic results, and a novel decremental approach. Lecture Notes in Computer Science, 2202:312-328, 2001. [ bib | http ]
The purpose of this paper is twofold. First, we review several basic combinatorial problems that have been stated in terms of directed hypergraphs and have been studied in the literature in the framework of different application domains. Among them, transitive closure, transitive reduction, flow and cut problems, and minimum weight traversal problems. For such problems we illustrate some of the most important algorithmic results in the context of both static and dynamic applications. Second, we address a specific dynamic problem which finds several interesting applications, especially in the framework of knowledge representation: the maintenance of minimum weight hyperpaths under hyperarc weight increases and hyperarc deletions. For such problem we provide a new efficient algorithm applicable for a wide class of hyperpath weight measures. Keywords: Directed hypergraph, minimum weight hyperpath, dynamic algorithm, AND/OR graph.

[3] S. Deb, M. Effros, T. Ho, D. R. Karger, R. Koetter, D. S. Lun, M. Médard, and N. Ratnakar. Network coding for wireless applications: A brief tutorial. In Proceedings of International Workshop on Wireless Ad-hoc Networks (IWWAN), May 2005. Invited paper. [ bib | .pdf ]
[4] G. Gallo, G. Longo, and S. Pallottino. Directed hypergraphs and applications. Discrete Applied Mathematics, 42(2):177-201, 1993. [ bib | .html ]
[5] G. Gallo and M. G. Scutella. Directed hypergraphs as a modelling paradigm. Technical Report TR-99-02, Department of Computer Science, University of Pisa, Italy, February 1999. [ bib | .html ]
[6] D. S. Lun, M. Médard, and D. R. Karger. On the dynamic multicast problem for coded networks. In Proceedings of the 1st Network Coding Workshop (NetCod), April 2005. [ bib | .pdf ]
[7] Network Coding Home Page [ bib | http ]
[8] Random Network Coding web site [ bib | http ]
[9] Y. Sagduyu and A. Ephremides. Joint scheduling and wireless network coding. In Proceedings of the 1st Network Coding Workshop (NetCod), April 2005. [ bib | .pdf ]
[10] M. Thakur and R. Tripathi. Complexity of linear connectivity problems in directed hypergraphs. In Proceedings of 24th International Conference in Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 3328 of Lecture Notes in Computer Science, pages 481-493. Springer, 2004. [ bib | DOI | .pdf ]
We introduce a notion of linear hyperconnection (formally denoted L-hyperpath) between nodes in a directed hypergraph and relate this notion to existing notions of hyperpaths in directed hypergraphs. We observe that many interesting questions in problem domains such as secret transfer protocols, routing in packet filtered networks, and propositional satisfiability are basically questions about existence of L-hyperpaths or about cyclomatic number of directed hypergraphs w.r.t. L-hypercycles (the minimum number of hyperedges that need to be deleted to make a directed hypergraph free of L-hypercycles). We prove that the L-hyperpath existence problem, the cyclomatic number problem, the minimum cyclomatic set problem, and the minimal cyclomatic set problem are each complete for a different level (respectively, NP, p2, p2, and DP) of the polynomial hierarchy.

[11] J. Widmer, C. Fragouli, and J.-Y. L. Boudec. Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding. In Proceedings of the 1st Network Coding Workshop (NetCod), April 2005. [ bib | .pdf ]
Energy efficiency, i.e., the amount of battery energy consumed to transmit bits across a wireless link, is a critical design parameter for wireless ad-hoc networks. This paper examines the problem of broadcasting information to all nodes in an ad-hoc network, when a large percentage of the nodes act as sources. For this application, we theoretically quantify the energy savings that network coding can offer in the cases of a line network and a rectangular grid network. We then propose low-complexity distributed algorithms, and demonstrate through simulation that in practice, for random networks, network coding can in fact offer significant benefits in terms of energy consumption.

[12] Y. Wu, P. A. Chou, and S. Y. Kung. Information exchange in wireless networks with network coding and physical-layer broadcast. Technical Report MSR-TR-2004-78, Microsoft Research, August 2004. [ bib | http ]
We show that mutual exchange of independent information between two nodes in a wireless network can be efficiently performed by exploiting network coding and the physical-layer broadcast property offered by the wireless medium. The proposed approach improves upon conventional solutions that separate the processing of the two unicast sessions, corresponding to information transfer along one direction and the opposite direction. We propose a simple and practical approach to realize the gain.

[13] Y. Wu, P. A. Chou, and S. Y. Kung. Information exchange in wireless networks with network coding and physical-layer broadcast. In Proceedings of the 39th Annual Conference on Information Sciences and Systems (CISS) [12]. [ bib ]

This file was generated by bibtex2html 1.96.

The .bib file was last modified on 14:46:10 Feb 11 2011