Inapproximability results related to monophonic convexity
From MaRDI portal
Publication:499364
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
NP-completenessbipartite graphsconvexity numberinapproximabilitypercolation timemonophonic convexity
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