On the approximation hardness of geodetic set and its variants
From MaRDI portal
Publication:2695276
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
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
