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)

zbMATH Keywords

shortest pathchordal graphsgeodesic convexityhull number

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Convexity in partial cubes: the hull number
• 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

(15)

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

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)