Computing simple-path convex hulls in hypergraphs

DOI10.1016/j.ipl.2010.11.026zbMath1259.05170OpenAlexW1964105054MaRDI 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 algorithmstotally balanced hypergraphssimple-path convex hullsimple-path convexity

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A new notion of convexity in digraphs with an application to Bayesian networks, Equivalence between hypergraph convexities, On the contour of graphs, On the geodeticity of the contour of a graph, CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT, 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

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