Node disjoint paths of minimum total lenght on 2-trees

The problem of finding p(and even 2) node disjoint paths on a digraph, connecting p pair of terminals is NP-complete. For directed k-trees however, the problem is polynomial. In this paper, we give a linear algorithm for the corresponding optimisation problem on 2-trees and for the case p=2, we characterize te convex hull of the corresponding edge incidence vectors. The optimization algorithm ramains linear and independent of p for k > or equal 3 if the terminals are distinct


    PRO 88.05, No dates


    • ROSO-REPORT-1988-001

    Notice créée le 2006-02-13, modifiée le 2016-08-08


  • Aucun fulltext n'est disponible. Veuillez contacter le laboratoire ou les auteurs.

Documents pertinents