On the approximation hardness of geodetic set and its variants

DOI10.1007/978-3-030-89543-3_7OpenAlexW3198211754MaRDI QIDQ2695276

Tom Davot, Jocelyn Thiebaut, Lucas Isenmann

Publication date: 30 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-89543-3_7

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong geodetic problem in grid-like architectures
• Hardness and approximation for the geodetic set problem in some graph classes
• Optimization, approximation, and complexity classes
• The geodetic number of a graph
• On residual approximation in solution extension problems
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}
• Strong edge geodetic problem on grids
• Strong geodetic problem in networks
• Strong geodetic cores and Cartesian product graphs
• Strong edge geodetic problem in networks
• The edge geodetic number of product graphs
• Comment on "Edge Geodetic Covers in Graphs
• Geodetic Sets in Graphs
• On The Edge Geodetic Number Of A Graph
• Strong geodetic problem on complete multipartite graphs
• Analytical approach to parallel repetition
• Edge geodetic number of a graph
• The edge geodetic number and Cartesian product of graphs

This page was built for publication: On the approximation hardness of geodetic set and its variants