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

This page was built for publication: Inapproximability results related to monophonic convexity