Given an undirected connected graph ๐บ = (๐ (๐บ), ๐ธ(๐บ)) on ๐ vertices, the minimum Monitoring Edge-Geodetic Set (MEG-set) problem asks to find a subset ๐ โ ๐ (๐บ) of minimum cardinality such that, for every edge ๐ โ ๐ธ(๐บ), there exist ๐ฅ, ๐ฆ โ ๐ for which all shortest paths between ๐ฅ and ๐ฆ in ๐บ traverse ๐. We show that, for any constant ๐ < 1/2, no polynomial-time (๐ log ๐)-approximation algorithm for the minimum MEG-set problem exists, unless P = NP.
On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets (short paper)
Bilo' D.;Colli G.;Forlizzi L.;Leucci S.
2024-01-01
Abstract
Given an undirected connected graph ๐บ = (๐ (๐บ), ๐ธ(๐บ)) on ๐ vertices, the minimum Monitoring Edge-Geodetic Set (MEG-set) problem asks to find a subset ๐ โ ๐ (๐บ) of minimum cardinality such that, for every edge ๐ โ ๐ธ(๐บ), there exist ๐ฅ, ๐ฆ โ ๐ for which all shortest paths between ๐ฅ and ๐ฆ in ๐บ traverse ๐. We show that, for any constant ๐ < 1/2, no polynomial-time (๐ log ๐)-approximation algorithm for the minimum MEG-set problem exists, unless P = NP.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
paper110.pdf
accesso aperto
Tipologia:
Documento in Versione Editoriale
Licenza:
Creative commons
Dimensione
1.29 MB
Formato
Adobe PDF
|
1.29 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
