Complexity analysis of P₃-convexity problems on bounded-degree and planar graphs

DOI10.1016/J.TCS.2015.10.003MaRDI QIDQ897965zbMATH OpenOpenAlexFDO

Authors Lucia Draque Penso, Dieter Rautenbach, Uéverton dos Santos Souza, Fábio Protti

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.003

zbMATH Keywords

NP-completenessparametrizationFPTW[2-hard]

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• On \(P_{3}\)-convexity of graphs with bounded degree
• The convexity of induced paths of order three and applications: complexity aspects
• On the complexity of the \(P_{3}\)-hull number of the Cartesian product of graphs
• Computing the \(\mathcal{P}_3\)-hull number of a graph, a polyhedral approach
• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Bounds on the \(k\)-domination number of a graph
• Constant thresholds can make target set selection tractable
• Geodetic number versus hull number in \(P_3\)-convexity
• Immediate versus eventual conversion: comparing geodetic and hull numbers in \(P _{3}\)-convexity
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• On 2-domination and independence domination numbers of graphs.
• On graphs with equal domination and 2-domination numbers
• On the approximability of influence in social networks
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Planar Formulae and Their Uses
• Random majority percolation
• Sharp thresholds in bootstrap percolation
• The power of small coalitions in graphs

Cited in

(13)

• On the \(P_3\)-hull number of some products of graphs
• Remarks on \(k\)-clique, \(k\)-independent set and 2-contamination in complementary prisms
• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• On the \(P_3\)-hull number of Hamming graphs
• Corrigendum to ``Complexity analysis of \(P_{3}\)-convexity problems on bounded-degree and planar graphs
• Efficient realizations of closure systems
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• On \(P_{3}\)-convexity of graphs with bounded degree
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs
• On the complexity of the \(P_{3}\)-hull number of the Cartesian product of graphs
• \(P_3\)-hull number of graphs with diameter two
• The convexity of induced paths of order three and applications: complexity aspects

This page was built for publication: Complexity analysis of \(P_3\)-convexity problems on bounded-degree and planar graphs

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