• A
• A
• A
• АБB
• АБB
• АБB
• А
• А
• А
• А
• А
Обычная версия сайта

## 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 -path we mean a path P such that P connects terminals from distinct sets in and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection ℘ of -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.