The maximum infection time in the geodesic and monophonic convexities

DOI10.1016/J.TCS.2015.10.009MaRDI QIDQ897893zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.10.009

zbMATH Keywords

geodesic convexitymaximum infection timemonophonic convexitymonophonic hull number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38)

Recommendations

• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• Complexity of determining the maximum infection time in the geodetic convexity
• The P3 infection time is W[1]-hard parameterized by the treewidth
• Inapproximability results related to monophonic convexity
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• An algorithm for finding clique cut-sets
• An introduction to clique minimal separator decomposition
• Bootstrap percolation in living neural networks
• Bootstrap percolation in three dimensions
• Complexity results related to monophonic convexity
• Convex sets in graphs. II: Minimal path convexity
• Convexity in Graphs and Hypergraphs
• Decomposition by clique separators
• Distance-hereditary graphs
• Growth rates and explosions in sandpiles
• Inapproximability results related to monophonic convexity
• 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 slowly percolating sets of minimal size in bootstrap percolation
• On the Carathéodory number for the convexity of paths of order three
• On the computation of the hull number of a graph
• Optimal decomposition by clique separators
• Sharp metastability threshold for two-dimensional bootstrap percolation
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• The complexity of theorem-proving procedures
• The hull number of a graph
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The sharp threshold for bootstrap percolation in all dimensions

Cited in

(7)

• Convex and isometric domination of (weak) dominating pair graphs
• A necessary condition for the equality of the clique number and the convexity number of a graph
• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• Complexity of determining the maximum infection time in the geodetic convexity
• On the hull number on cycle convexity of graphs
• Target set selection with maximum activation time
• The P3 infection time is W[1]-hard parameterized by the treewidth

This page was built for publication: The maximum infection time in the geodesic and monophonic convexities

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