Computing simple-path convex hulls in hypergraphs

DOI10.1016/j.ipl.2010.11.026zbMath1259.05170MaRDI QIDQ1944079

Mauro Mezzini, Marina Moscarini, Francesco Mario Malvestuto

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.11.026

zbMATH Keywords

graph algorithms; totally balanced hypergraphs; simple-path convex hull; simple-path convexity

Mathematics Subject Classification ID

05C65: Hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT, A new notion of convexity in digraphs with an application to Bayesian networks, Equivalence between hypergraph convexities, On the geodeticity of the contour of a graph, Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs, An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs, On the contour of graphs

Cites Work

• Unnamed Item
• Canonical and monophonic convexities in hypergraphs
• Convex sets in graphs. II: Minimal path convexity
• On triangle path convexity in graphs
• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• Steiner distance and convexity in graphs
• The All-Paths Transit Function of a Graph
• Characterizations of totally balanced matrices
• Steiner Trees and Convex Geometries
• Convexity in Graphs and Hypergraphs