کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478279 | 1446046 | 2013 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Finding hypernetworks in directed hypergraphs Finding hypernetworks in directed hypergraphs](/preview/png/478279.png)
• Theoretical and computational relevance of hypernetworks.
• Relations to other concepts, namely, flow hypergraphs and dominators.
• A simple and fast method for finding the s-hypernetwork.
• Linear time methods for s-hypernetworks in acyclic hypergraphs and directed graphs.
• A linear time method for the (s, d)-hypernetwork in acyclic hypergraphs.
The term “hypernetwork” (more precisely, s-hypernetwork and (s, d)-hypernetwork) has been recently adopted to denote some logical structures contained in a directed hypergraph. A hypernetwork identifies the core of a hypergraph model, obtained by filtering off redundant components. Therefore, finding hypernetworks has a notable relevance both from a theoretical and from a computational point of view.In this paper we provide a simple and fast algorithm for finding s-hypernetworks, which substantially improves on a method previously proposed in the literature. We also point out two linearly solvable particular cases.Finding an (s, d)-hypernetwork is known to be a hard problem, and only one polynomially solvable class has been found so far. Here we point out that this particular case is solvable in linear time.
Journal: European Journal of Operational Research - Volume 230, Issue 2, 16 October 2013, Pages 226–230