In a connected hypergraph a vertex set X is simple-path convex (sp-convex, for short) if either |X|≤1 or X contains every vertex on every simple path between two vertices in X (Faber and Jamison, 1986 [7]), and the sp-convex hull of a vertex set X is the minimal superset of X that is sp-convex. In this paper, we give a polynomial algorithm to compute sp-convex hulls in an arbitrary hypergraph. © 2010 Elsevier B.V.

Francesco Mario, M., Mezzini, M., Marina, M. (2011). Computing simple-path convex hulls in hypergraphs. INFORMATION PROCESSING LETTERS, 111(5), 231-234 [10.1016/j.ipl.2010.11.026].

Computing simple-path convex hulls in hypergraphs

MEZZINI, MAURO;
2011

Abstract

In a connected hypergraph a vertex set X is simple-path convex (sp-convex, for short) if either |X|≤1 or X contains every vertex on every simple path between two vertices in X (Faber and Jamison, 1986 [7]), and the sp-convex hull of a vertex set X is the minimal superset of X that is sp-convex. In this paper, we give a polynomial algorithm to compute sp-convex hulls in an arbitrary hypergraph. © 2010 Elsevier B.V.
Francesco Mario, M., Mezzini, M., Marina, M. (2011). Computing simple-path convex hulls in hypergraphs. INFORMATION PROCESSING LETTERS, 111(5), 231-234 [10.1016/j.ipl.2010.11.026].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/155438
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact