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.

Finding hypernetworks in directed hypergraphs / Pretolani, Daniele. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 230(2013), pp. 226-230. [10.1016/j.ejor.2013.04.020]

I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021