On the computation of the hull number of a graph

DOI10.1016/j.disc.2008.04.020zbMath1215.05184OpenAlexW2068911038MaRDI QIDQ1045055

Mitre C. Dourado, Fábio Protti, Jan Kratochvíl, John G. Gimbel, Jayme Luiz Szwarcfiter

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.04.020

zbMATH Keywords

complexity algorithms convexity geodesics cographs hull number unit interval graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A polynomial time algorithm for geodetic hull number for complementary prisms ⋮ Complexity aspects of the triangle path convexity ⋮ \(P_3\)-hull number of graphs with diameter two ⋮ Hull number: \(P_5\)-free graphs and reduction rules ⋮ 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 ⋮ Geodeticity of the contour of chordal bipartite graphs ⋮ 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 ⋮ The geodetic hull number is hard for chordal graphs ⋮ Convex Partitions of Graphs ⋮ Algorithmic Aspects of Monophonic Convexity ⋮ Maximal closed set and half-space separations in finite closure systems ⋮ On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent ⋮ The maximum infection time in the geodesic and monophonic convexities ⋮ Convex \(p\)-partitions of bipartite graphs ⋮ On the geodetic iteration number of distance-hereditary graphs ⋮ Convexity in partial cubes: the hull number ⋮ Computing the hull and interval numbers in the weakly toll convexity ⋮ On the geodetic and the hull numbers in strong product graphs ⋮ The Geodetic Hull Number is Hard for Chordal Graphs ⋮ Computing the hull number in \(\Delta \)-convexity ⋮ Geodetic convexity and Kneser graphs ⋮ On the contour of graphs ⋮ Towards a new framework for domination ⋮ Graphs with a minimal number of convex sets ⋮ CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT ⋮ On the contour of bipartite graphs ⋮ Unnamed Item ⋮ On the parameterized complexity of the geodesic hull number ⋮ Partitioning a graph into convex sets ⋮ Complexity results related to monophonic convexity ⋮ Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs ⋮ Vector domination in split-indifference graphs ⋮ Geodetic convexity parameters for \((q, q - 4)\)-graphs ⋮ On the Carathéodory and exchange numbers of geodetic convexity in graphs ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ Computational and structural aspects of the geodetic and the hull numbers of shadow graphs ⋮ Computational and structural aspects of the geodetic and the hull numbers of shadow graphs ⋮ Hull and geodetic numbers for some classes of oriented graphs ⋮ Hull and geodetic numbers for some classes of oriented graphs ⋮ On the Convexity of Paths of Length Two in Undirected Graphs ⋮ The hull number in the convexity of induced paths of order \(3\) ⋮ Complexity aspects of \(\ell\)-chord convexities ⋮ On the spectrum and number of convex sets in graphs ⋮ On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs ⋮ THE HULL NUMBER OF POWERS OF CYCLES ⋮ An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs

Cites Work