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

DOI10.1142/S1793830918500428zbMATH Open1400.05132OpenAlexW2795031152WikidataQ130059358 ScholiaQ130059358MaRDI QIDQ4554573FDOQ4554573

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

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

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)

Cites Work

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

Cited In (4)

• A necessary condition for the equality of the clique number and the convexity number of a graph
• 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
• 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)