Complexity results related to monophonic convexity
From MaRDI portal
Publication:987671
DOI10.1016/j.dam.2009.11.016zbMath1209.05130OpenAlexW1973562342MaRDI QIDQ987671
Mitre C. Dourado, Fábio Protti, Jayme Luiz Szwarcfiter
Publication date: 13 August 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.11.016
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 ⋮ On the computational complexity of the Helly number in the \(P_3\) and related convexities ⋮ \(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 geodetic hull number of \(P_{k}\)-free graphs ⋮ On the \(P_3\)-hull number of some products of graphs ⋮ And/or-convexity: a graph convexity based on processes and deadlock models ⋮ Geodetic Convexity Parameters for Graphs with Few Short Induced Paths ⋮ Complexity of determining the maximum infection time in the geodetic convexity ⋮ Two classes of graphs in which some problems related to convexity are efficiently solvable ⋮ A general framework for path convexities ⋮ Computing the hull number in toll convexity ⋮ On the toll number of a graph ⋮ \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers ⋮ Extreme-support total monophonic graphs ⋮ Inapproximability results and bounds for the Helly and Radon numbers of a graph ⋮ On the Carathéodory number of interval and graph convexities ⋮ On the \(P_3\)-hull number of Hamming graphs ⋮ On the monophonic rank of a graph ⋮ The maximum infection time in the geodesic and monophonic convexities ⋮ Computing the hull and interval numbers in the weakly toll convexity ⋮ Segment transit function of the induced path function of graphs and its first-order definability ⋮ On the monophonic convexity in complementary prisms ⋮ Domination and convexity problems in the target set selection model ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ The P3 infection time is W[1-hard parameterized by the treewidth] ⋮ Computing the hull number in \(\Delta \)-convexity ⋮ Geodetic convexity and Kneser graphs ⋮ Decomposable convexities in graphs and hypergraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Carathéodory number of the \(P_3\) convexity of chordal graphs ⋮ Computing the \(\mathcal{P}_3\)-hull number of a graph, a polyhedral approach ⋮ Graphs with a minimal number of convex sets ⋮ Inapproximability results related to monophonic convexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On finite convexity spaces induced by sets of paths in graphs ⋮ Unnamed Item ⋮ On the parameterized complexity of the geodesic hull number ⋮ Partitioning a graph into convex sets ⋮ Geodetic convexity parameters for \((q, q - 4)\)-graphs ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ On the \(P_3\)-hull number of Kneser graphs ⋮ Covering graphs with convex sets and partitioning graphs into convex sets ⋮ The hull number in the convexity of induced paths of order \(3\) ⋮ Complexity aspects of \(\ell\)-chord convexities ⋮ Convex geometries over induced paths with bounded length ⋮ Minimal connected restrained monophonic sets in graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Helly theorem for convexity in graphs
- Chordless paths through three vertices
- Some remarks on the geodetic number of a graph
- On the computation of the hull number of a graph
- Decomposition by clique separators
- The theory of convex geometries
- On local convexity in graphs
- Convex sets in graphs. II: Minimal path convexity
- An algorithm for finding clique cut-sets
- Algorithms on clique separable graphs
- Separation of two convex sets in convexity structures
- Some remarks on the convexity number of a graph
- Convexities related to path properties on graphs
- On the Hull Number of Triangle-Free Graphs
- On the metric dimension of some families of graphs
- Convexity in Graphs and Hypergraphs
- Computational Complexity of Geodetic Set
