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.

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, ^p₂, ^p₂, and DP) of the polynomial hierarchy.

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.

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.