Inapproximability results related to monophonic convexity

DOI10.1016/j.dam.2014.09.012zbMath1321.05128OpenAlexW2039031503MaRDI QIDQ499364

Mitre C. Dourado, Eurinardo R. Costa, Rudini Menezes Sampaio

Publication date: 30 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.09.012

zbMATH Keywords

NP-completenessbipartite graphsconvexity numberinapproximabilitypercolation timemonophonic convexity

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Complexity aspects of the triangle path convexity, A necessary condition for the equality of the clique number and the convexity number of a graph, \(P_3\)-hull number of graphs with diameter two, The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree, On the \(P_3\)-hull number of some products of graphs, \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers, Extreme-support total monophonic graphs, Target set selection with maximum activation time, The maximum infection time in the geodesic and monophonic convexities, On the monophonic convexity in complementary prisms, The P3 infection time is W[1-hard parameterized by the treewidth], Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Preface, Minimal connected restrained monophonic sets in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On slowly percolating sets of minimal size in bootstrap percolation
• Complexity results related to monophonic convexity
• Convex sets in graphs. II: Minimal path convexity
• Convexity in graphs
• An introduction to clique minimal separator decomposition
• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• Optimal decomposition by clique separators
• The connected monophonic number of a graph
• Linear degree extractors and the inapproximability of max clique and chromatic number
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Euclidean Distance Geometry and Applications