The geodetic hull number is hard for chordal graphs

DOI10.1137/17M1131726MaRDI QIDQ4604645zbMATH OpenWikidataFDO

Authors Stéphane Bessy, Mitre C. Dourado, Dieter Rautenbach, Lucia Draque Penso

Publication date 5 March 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17M1131726

zbMATH Keywords

chordal graphsgeodesic convexityhull numbershortest path

Mathematics Subject Classification ID

Distance in graphs (05C12) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• On the geodetic hull number of \(P_{k}\)-free graphs
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• On the hull number of some graph classes
• On the parameterized complexity of the geodesic hull number

Cites work

• Convexity in partial cubes: the hull number
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Hull number: \(P_5\)-free graphs and reduction rules
• On the computation of the hull number of a graph
• On the geodetic hull number of \(P_{k}\)-free graphs
• On the hull number of some graph classes
• On the hull number of triangle-free graphs
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• The hull number of a graph

Cited in

(16)

• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• The hull number in the convexity of induced paths of order \(3\)
• Computing the hull number in toll convexity
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• Computing the hull number in -convexity
• On the parameterized complexity of the geodesic hull number
• On the geodetic hull number of \(P_{k}\)-free graphs
• A polynomial time algorithm for geodetic hull number for complementary prisms
• Parameterized complexity of geodetic set
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• Hull and geodetic numbers for some classes of oriented graphs
• Hull and geodetic numbers for some classes of oriented graphs
• Parameterized Complexity of Geodetic Set
• Bounds and algorithms for geodetic hulls
• Improved bounds for geodetic hulls

This page was built for publication: The geodetic hull number is hard for chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604645)