New algorithms for maximum disjoint paths based on tree-likeness

We study the classical [Formula: see text] -hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; t...

Descripción completa

Detalles Bibliográficos
Autores principales: Fleszar, Krzysztof, Mnich, Matthias, Spoerhase, Joachim
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer Berlin Heidelberg 2017
Materias:
Full Length Paper
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6417437/
https://www.ncbi.nlm.nih.gov/pubmed/30956356
http://dx.doi.org/10.1007/s10107-017-1199-3

Internet

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6417437/
https://www.ncbi.nlm.nih.gov/pubmed/30956356
http://dx.doi.org/10.1007/s10107-017-1199-3

Ejemplares similares