Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs

DOI10.1016/j.tcs.2018.05.032zbMath1401.05285OpenAlexW2805872963WikidataQ129737807 ScholiaQ129737807MaRDI QIDQ1786594

Mauro Mezzini

Publication date: 24 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.05.032

zbMATH Keywords

geodetic numbergeodesic convexityouterplanar graphgeodetic setgeodetic hull numbergeodetic hull set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Well-partitioned chordal graphs ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ Three problems on well-partitioned chordal graphs ⋮ On the approximation hardness of geodetic set and its variants ⋮ Unnamed Item ⋮ An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs

Cites Work

• Unnamed Item
• Hull number: \(P_5\)-free graphs and reduction rules
• Some remarks on the geodetic number of a graph
• Canonical and monophonic convexities in hypergraphs
• On the computation of the hull number of a graph
• The hull number of a graph
• On local convexity in graphs
• Bridged graphs and geodesic convexity
• Convex sets in graphs. II: Minimal path convexity
• Characterizations of outerplanar graphs
• The geodetic number of a graph
• On the hull number of some graph classes
• Computing simple-path convex hulls in hypergraphs
• On the geodetic hull number of \(P_{k}\)-free graphs
• Geodesic Convexity in Graphs
• Block decomposition approach to compute a minimum geodetic set
• On the Hull Number of Triangle-Free Graphs
• Determining outerplanarity using segment graphs
• Convexity in Graphs and Hypergraphs
• Convexity and HHD-Free Graphs
• The Geodetic Hull Number is Hard for Chordal Graphs
• CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT
• Convexity in Partial Cubes: The Hull Number
• Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs

This page was built for publication: Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs