Complexity of determining the maximum infection time in the geodetic convexity

DOI10.1016/J.ENDM.2015.07.067zbMath1347.05041OpenAlexW2209105919MaRDI QIDQ324866

Mohammad Hasan, M. Dambrine

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity results related to monophonic convexity
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• On the computation of the hull number of a graph
• The hull number of a graph
• Distance-hereditary graphs
• On local convexity in graphs
• Convex sets in graphs. II: Minimal path convexity
• Algorithms on clique separable graphs
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On the Carathéodory Number for the Convexity of Paths of Order Three

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