Complexity of determining the maximum infection time in the geodetic convexity

DOI10.1016/J.ENDM.2015.07.067MaRDI QIDQ324866zbMATH OpenOpenAlexFDO

Authors F. S. Benevides, Victor Campos, Mitre C. Dourado, Ana Silva

Publication date 17 October 2016

Full work available at URL https://doi.org/10.1016/j.endm.2015.07.067

zbMATH Keywords

NP-completenessgeodetic convexitymaximum infection time

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) General convexity (52A99)

Recommendations

• The maximum infection time in the geodesic and monophonic convexities
• scientific article; zbMATH DE number 5531985
• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• On the convexity number of graphs
• The convexity of induced paths of order three and applications: complexity aspects

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 6302977 (Why is no real title available?)
• Algorithms on clique separable graphs
• Complexity results related to monophonic convexity
• Convex sets in graphs. II: Minimal path convexity
• Distance-hereditary graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On local convexity in graphs
• On the Carathéodory number for the convexity of paths of order three
• On the computation of the hull number of a graph
• The hull number of a graph

Cited in

(2)

• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• The maximum infection time in the geodesic and monophonic convexities

This page was built for publication: Complexity of determining the maximum infection time in the geodetic convexity

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