Two classes of graphs in which some problems related to convexity are efficiently solvable

DOI10.1142/S1793830918500428MaRDI QIDQ4554573zbMATH OpenOpenAlexWikidataFDO

Authors Marina Moscarini, Francesco M. Malvestuto

Publication date 14 November 2018

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830918500428

zbMATH Keywords

geodesic convexitydistance-hereditary graphsmonophonic convexity2-geodesic convexitycross-cyclic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Recommendations

• On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent
• Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent
• On the hull number of some graph classes
• Algorithmic Aspects of Monophonic Convexity
• Complexity results related to monophonic convexity

Cites work

• scientific article; zbMATH DE number 1064241 (Why is no real title available?)
• Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent
• Complexity results related to monophonic convexity
• Convex sets in a graph
• Convex sets in graphs. II: Minimal path convexity
• Convexity in Graphs and Hypergraphs
• Decomposition by clique separators
• Equivalence between hypergraph convexities
• On the computation of the hull number of a graph
• Optimal decomposition by clique separators
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• The All-Paths Transit Function of a Graph

Cited in

(4)

• On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent
• On the geodetic iteration number of distance-hereditary graphs
• A necessary condition for the equality of the clique number and the convexity number of a graph
• Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent

This page was built for publication: Two classes of graphs in which some problems related to convexity are efficiently solvable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554573)