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

DOI10.1016/J.TCS.2018.05.032zbMATH Open1401.05285OpenAlexW2805872963WikidataQ129737807 ScholiaQ129737807MaRDI QIDQ1786594FDOQ1786594

Authors 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

geodesic convexitygeodetic setouterplanar graphgeodetic numbergeodetic hull numbergeodetic hull set

Mathematics Subject Classification ID

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

Recommendations

• An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs
• Computing minimum geodetic sets of proper interval graphs
• Some remarks on the geodetic number of a graph
• Hardness and approximation for the geodetic set problem in some graph classes
• scientific article; zbMATH DE number 5531985

Cites Work

• scientific article; zbMATH DE number 3697163 (Why is no real title available?)
• Block decomposition approach to compute a minimum geodetic set
• Bridged graphs and geodesic convexity
• Canonical and monophonic convexities in hypergraphs
• Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent
• Characterizations of outerplanar graphs
• Computing simple-path convex hulls in hypergraphs
• Convex sets in graphs. II: Minimal path convexity
• Convexity and HHD-Free Graphs
• Convexity in Graphs and Hypergraphs
• Convexity in partial cubes: the hull number
• Determining outerplanarity using segment graphs
• Geodesic Convexity in Graphs
• Hull number: \(P_5\)-free graphs and reduction rules
• On local convexity in graphs
• 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
• Some remarks on the geodetic number of a graph
• The geodetic hull number is hard for chordal graphs
• The geodetic number of a graph
• The hull number of a graph

Cited In (8)

• An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs
• Well-partitioned chordal graphs
• Algorithms and complexity for geodetic sets on partial grids
• Computing minimum geodetic sets of proper interval graphs
• Three problems on well-partitioned chordal graphs
• Maintaining the minimal distance of a point set in polylogarithmic time
• Title not available (Why is no real title available?)
• On the approximation hardness of geodetic set and its variants

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

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