In this paper the problem of minimal representations for particular classes of directed hypergraphs is analyzed. Various concepts of minimal representations of directed hypergraphs (called minimal equivalent hypergraphs) are introduced as extensions to the concepts of transitive reduction and minimum equivalent graph of directed graphs. In particular, we consider equivalent hypergraphs which are minimal with respect to all parameters which may be adopted to characterize a given hypergraph (number of hyperarcs, number of adjacency lists required for the representation, length of the overall description, etc. ). The relationships among the various concepts of minimality are discussed and their computational properties are analyzed. In order to derive such results, a graph representation of hypergraphs is introduced.
MINIMAL REPRESENTATION OF DIRECTED HYPERGRAPHS / Ausiello, G.; D'Atri, A.; Sacca', Domenico. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 15:2(1986), pp. 418-431.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | MINIMAL REPRESENTATION OF DIRECTED HYPERGRAPHS |
Autori: | |
Data di pubblicazione: | 1986 |
Rivista: | |
Citazione: | MINIMAL REPRESENTATION OF DIRECTED HYPERGRAPHS / Ausiello, G.; D'Atri, A.; Sacca', Domenico. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 15:2(1986), pp. 418-431. |
Handle: | http://hdl.handle.net/20.500.11770/145332 |
Appare nelle tipologie: | 1.1 Articolo in rivista |