A Fast Algorithm for the Path 2-Packing Problem
Theory of Computing Systems. 2010. No. 46(1). P. 59-79.
Let G be an undirected graph and be a collection of disjoint subsets of nodes. Nodes in T 1∪⋅⋅⋅∪T k are called terminals, other nodes are called inner. By a TeX -path we mean a path P such that P connects terminals from distinct sets in TeX and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection ℘ of TeX -paths such that at most two paths in ℘ pass through any node. Our algorithm is purely combinatorial and has the time complexity O(mn 2), where n and m denote the numbers of nodes and edges in G, respectively.