Complexity analysis of \(P_3\)-convexity problems on bounded-degree and planar graphs
From MaRDI portal
Publication:897965
DOI10.1016/j.tcs.2015.10.003zbMath1332.68059OpenAlexW2209387264MaRDI QIDQ897965
Uéverton dos Santos Souza, Dieter Rautenbach, Lucia Draque Penso, 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
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
\(P_3\)-hull number of graphs with diameter two ⋮ On the \(P_3\)-hull number of some products of graphs ⋮ A general framework for path convexities ⋮ Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs ⋮ \(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 \(P_3\)-hull number of Hamming graphs ⋮ Deadlock resolution in wait-for graphs by vertex/arc deletion ⋮ Efficient realizations of closure systems ⋮ On the complexity of the \(P_{3}\)-hull number of the Cartesian product of graphs ⋮ Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Irreversible conversion of graphs
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- 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
- Bounds on the \(k\)-domination number of a graph
- On graphs with equal domination and 2-domination numbers
- Geodetic Number versus Hull Number in $P_3$-Convexity
- Random majority percolation
- On the Approximability of Influence in Social Networks
- Planar Formulae and Their Uses
- Constant Thresholds Can Make Target Set Selection Tractable
- Immediate versus Eventual Conversion: Comparing Geodetic and Hull Numbers in P 3-Convexity
