On the computational complexity of the Helly number in the \(P_3\) and related convexities

DOI10.1016/j.entcs.2019.08.026OpenAlexW2978611037WikidataQ113317406 ScholiaQ113317406MaRDI QIDQ2132356

Simone Dantas, Mitre C. Dourado, Moisés T. Carvalho, Jayme Luiz Szwarcfiter, Daniel F. D. Posner

Publication date: 27 April 2022

Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.026

zbMATH Keywords

cliques\(P_3\)-Helly-independentdominating and independent sets

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Related Items

Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs ⋮ Domination and convexity problems in the target set selection model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent domination in hereditary classes
• Approximability results for the maximum and minimum maximal induced matching problems
• Complexity results related to monophonic convexity
• NP-completeness of some generalizations of the maximum matching problem
• Local majorities, coalitions and monopolies in graphs: A review
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Complexity aspects of the Helly property: graphs and hypergraphs
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• The Carathéodory number of the \(P_3\) convexity of chordal graphs
• Bipartite Domination and Simultaneous Matroid Covers
• An induced subgraph characterization of domination perfect graphs
• The P k Partition Problem and Related Problems in Bipartite Graphs