@Misc{networkcoding-site,
key = {NC},
note = {Network Coding Home Page \href{http://www.networkcoding.info}{http://www.networkcoding.info}},
url = {http://www.networkcoding.info},
}
@Misc{randomnetworkcoding-site,
key = {RNC},
note = {Random Network Coding web site \href{http://www.mit.edu/~medard/coding1.htm}{http://www.mit.edu/\symbol{126}medard/coding1.htm}},
url = {http://www.mit.edu/~medard/coding1.htm},
}
@article{DBLP:journals/tit/AhlswedeCLY00,
author = {Rudolf Ahlswede and Ning Cai and Shuo-Yen Robert Li and Raymond W. Yeung},
title = {Network information flow.},
journal = {IEEE Transactions on Information Theory},
volume = {46},
number = {4},
year = {2000},
month = {July},
pages = {1204-1216},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@InProceedings{widmer2005,
author = {J. Widmer and C. Fragouli and J.-Y. Le Boudec},
title = {Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding},
booktitle = {Proceedings of the 1st Network Coding Workshop (NetCod)},
OPTpages = {},
year = {2005},
month = {April},
annote = {Alternative title: ``Energy-efficient broadcasting in wireless ad-hoc networks''},
abstract = {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.},
pdf = {http://www.netcod.org/papers/18WidmerFL-final.pdf},
}
@InProceedings{SagduyuEphremides2005,
author = {Y. Sagduyu and A. Ephremides},
title = {Joint scheduling and wireless network coding},
booktitle = {Proceedings of the 1st Network Coding Workshop (NetCod)},
OPTpages = {},
year = {2005},
month = {April},
OPTabstract = {},
pdf = {http://www.netcod.org/papers/01SagduyuE-final.pdf},
}
@InProceedings{deb2005,
author = {S. Deb and M. Effros and T. Ho and D. R. Karger and R. Koetter and D. S. Lun and M. M\'edard and N. Ratnakar},
title = {Network coding for wireless applications: A brief tutorial},
booktitle = {Proceedings of International Workshop on Wireless Ad-hoc Networks (IWWAN)},
OPTpages = {},
year = {2005},
month = {May},
note = {Invited paper},
pdf = {www.mit.edu/~dslun/publications/iwwan2005.pdf},
}
@TechReport{WuChouKung2004,
author = {Yunnan Wu and Philip A. Chou and S. Y. Kung},
title = {Information Exchange in Wireless Networks with Network Coding and Physical-layer Broadcast},
institution = {Microsoft Research},
crossref = {WuChouKung2005},
year = {2004},
number = {MSR-TR-2004-78},
month = {August},
annote = {also published as paper in CISS 2005},
http = {http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id=782},
abstract = {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.},
}
@InProceedings{WuChouKung2005,
author = {Yunnan Wu and Philip A. Chou and S. Y. Kung},
title = {Information exchange in wireless networks with network coding and physical-layer broadcast},
booktitle = {Proceedings of the 39th Annual Conference on Information Sciences and Systems (CISS)},
crossref = {WuChouKung2004},
OPTpages = {},
year = {2005},
month = {March},
}
@InProceedings{Lun2005,
author = {D. S. Lun and M. M\'edard and D. R. Karger},
title = {On the dynamic multicast problem for coded networks},
booktitle = {Proceedings of the 1st Network Coding Workshop (NetCod)},
OPTpages = {},
year = {2005},
month = {April},
OPTabstract = {},
pdf = {http://www.mit.edu/~dslun/publications/netcod2005_lun.pdf},
pdf = {http://www.netcod.org/papers/14LunMK-final.pdf},
}
%%%% Hypergraphs
@Article{Ausiello:2001:DHP,
author = {Giorgio Ausiello and Paolo G. Franciosa and Daniele Frigioni},
title = {Directed Hypergraphs: Problems, Algorithmic Results, and a Novel Decremental Approach},
journal = {Lecture Notes in Computer Science},
volume = {2202},
pages = {312--328},
year = {2001},
publisher = {Springer-Verlag GmbH},
editors = {A. Restivo and S. Ronchi Della Rocca and L. Roversi},
abstract = {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.},
CODEN = {LNCSD9},
ISSN = {0302-9743},
HTTP = {http://link.springer-ny.com/link/service/series/0558/bibs/2202/22020312.htm},
}
@article{gallo93directed,
author = {Giorgio Gallo and Giustino Longo and Stefano Pallottino},
title = {Directed Hypergraphs and Applications},
journal = {Discrete Applied Mathematics},
volume = {42},
number = {2},
pages = {177--201},
year = {1993},
http = {http://citeseer.ist.psu.edu/gallo92directed.html},
}
@techreport{gallo99directed,
author = {Giorgio Gallo and Maria Grazia Scutella},
title = {Directed Hypergraphs as a Modelling Paradigm},
number = {TR-99-02},
month = {February},
institution = {Department of Computer Science, University of Pisa, Italy},
year = {1999},
http = {http://citeseer.ist.psu.edu/gallo99directed.html},
}
@inproceedings{DBLP:conf/fsttcs/ThakurT04,
author = {Mayur Thakur and Rahul Tripathi},
title = {Complexity of Linear Connectivity Problems in Directed Hypergraphs.},
booktitle = {Proceedings of 24th International Conference in Foundations of Software Technology and Theoretical Computer Science (FSTTCS)},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {3328},
year = {2004},
isbn = {3-540-24058-6},
pages = {481--493},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {web.umr.edu/~thakurk/publications/hypergraph-c.pdf},
abstract = {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$, $\sum^p_2$, $\prod^p_2$, and $DP$) of the polynomial hierarchy.},
doi = {http://dx.doi.org/10.1007/b104325},
}