Parameterized Complexity of Directed Spanner Problems

We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance between any two vertices in H is at most t times the distance between these ve...

Descripción completa

Detalles Bibliográficos
Autores principales: Fomin, Fedor V., Golovach, Petr A., Lochet, William, Misra, Pranabendu, Saurabh, Saket, Sharma, Roohani
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2021
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9304079/
https://www.ncbi.nlm.nih.gov/pubmed/35880198
http://dx.doi.org/10.1007/s00453-021-00911-x

Internet

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9304079/
https://www.ncbi.nlm.nih.gov/pubmed/35880198
http://dx.doi.org/10.1007/s00453-021-00911-x

Ejemplares similares