We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph G and a collection of k source-destination pairs M = (s_1, t_1), ., (s_k, t_k). The goal is to maximize the number of pairs that can be routed subject to the capacities in the graph. A routing of a subset M' of the pairs is a collection P of paths such that, for each pair (s_i, t_i) in M', there is a path in P connecting s_i to t_i. In the Maximum Edge Disjoint Paths (MaxEDP) problem, the graph G has capacities cap(e) on the edges and a routing P is feasible if each edge e is in at most cap(e) of the paths of P. The Maximum Node Disjoint Paths (MaxNDP) problem is the node-capacitated counterpart of MaxEDP. In this paper we obtain an O(r^3) approximation for MaxEDP on graphs of treewidth at most r and a matching approximation for MaxNDP on graphs of pathwidth at most r. Our results build on and significantly improve the work by Chekuri et al. [ICALP 2013] who obtained an O(r * 3^r) approximation for MaxEDP.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    On Routing Disjoint Paths in Bounded Treewidth Graphs


    Beteiligte:
    Ene, Alina (Autor:in) / Mnich, Matthias (Autor:in) / Pilipczuk, Marcin (Autor:in) / Risteski, Andrej (Autor:in)

    Erscheinungsdatum :

    2016-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    000 / 004 / 629




    Robustly disjoint paths with segment routing

    Aubry, François / Vissicchio, Stefano / Bonaventure, Olivier et al. | BASE | 2018

    Freier Zugriff

    Non-Pool-Based Line Planning on Graphs of Bounded Treewidth

    Heinrich, Irene / Schiewe, Philine / Seebach, Constantin | DataCite | 2023

    Freier Zugriff

    The Complexity of Packing Edge-Disjoint Paths

    Dreier, Jan / Fuchs, Janosch / Hartmann, Tim A. et al. | BASE | 2019

    Freier Zugriff

    Disjoint Multipath Routing and Failure Recovery

    Oh Lee, Yong / Narasimha Reddy, A.L. | BASE | 2010

    Freier Zugriff

    Finding Edge-disjoint Paths in Networks: An Ant Colony Optimization Algorithm

    Blesa, M. J. / Blum, C. | British Library Online Contents | 2007