[1]  R. Ahlswede, N. Cai, S.Y. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):12041216, 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:312328, 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 Adhoc 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):177201, 1993. [ bib  .html ] 
[5]  G. Gallo and M. G. Scutella. Directed hypergraphs as a modelling paradigm. Technical Report TR9902, 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 http://www.networkcoding.info. [ bib  http ] 
[8]  Random Network Coding web site http://www.mit.edu/~medard/coding1.htm. [ 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 481493. Springer,
2004.
[ bib 
DOI 
.pdf ]
We introduce a notion of linear hyperconnection (formally denoted Lhyperpath) 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 Lhyperpaths or about cyclomatic number of directed hypergraphs w.r.t. Lhypercycles (the minimum number of hyperedges that need to be deleted to make a directed hypergraph free of Lhypercycles). We prove that the Lhyperpath 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, ^{p}_{2}, ^{p}_{2}, and DP) of the polynomial hierarchy.

[11] 
J. Widmer, C. Fragouli, and J.Y. L. Boudec.
Lowcomplexity energyefficient broadcasting in wireless adhoc
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 adhoc networks. This paper examines the problem of broadcasting information to all nodes in an adhoc 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 lowcomplexity 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
physicallayer broadcast.
Technical Report MSRTR200478, 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 physicallayer 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 physicallayer broadcast. In Proceedings of the 39th Annual Conference on Information Sciences and Systems (CISS) [12]. [ bib ] 
This file was generated by bibtex2html 1.96.