Complexity analysis of P₃-convexity problems on bounded-degree and planar graphs
DOI10.1016/J.TCS.2015.10.003zbMATH Open1332.68059OpenAlexW2209387264MaRDI QIDQ897965FDOQ897965
Uéverton dos Santos Souza, Dieter Rautenbach, Fábio Protti, Lucia Draque Penso
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
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bounds on the \(k\)-domination number of a graph
- On the Approximability of Influence in Social Networks
- Planar Formulae and Their Uses
- Constant Thresholds Can Make Target Set Selection Tractable
- Title not available (Why is that?)
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Irreversible conversion of graphs
- Random majority percolation
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Sharp thresholds in bootstrap percolation
- The power of small coalitions in graphs
- On graphs with equal domination and 2-domination numbers
- Geodetic number versus hull number in \(P_3\)-convexity
- On 2-domination and independence domination numbers of graphs.
- Immediate versus Eventual Conversion: Comparing Geodetic and Hull Numbers in P 3-Convexity
Cited In (11)
- Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs
- Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms
- On the \(P_3\)-hull number of some products of graphs
- \(P_3\)-hull number of graphs with diameter two
- On the \(P_3\)-hull number of Hamming graphs
- A general framework for path convexities
- Deadlock resolution in wait-for graphs by vertex/arc deletion
- Efficient realizations of closure systems
- \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
- Corrigendum to ``Complexity analysis of \(P_{3}\)-convexity problems on bounded-degree and planar graphs
- On the complexity of the \(P_{3}\)-hull number of the Cartesian product of graphs
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)
