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.
Computing simple-path convex hulls in hypergraphs / Malvestuto, Francesco Mario; Mauro, Mezzini; Moscarini, Marina. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 111:5(2011), pp. 231-234. [10.1016/j.ipl.2010.11.026]
Computing simple-path convex hulls in hypergraphs
MALVESTUTO, Francesco Mario;MOSCARINI, Marina
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
