Computer Science – Discrete Mathematics
Scientific paper
2008-09-21
Computer Science
Discrete Mathematics
18 pages, 5 figures in .eps format, 2 latex files, main file is kc13.tex Resubmission due to incorrectly specified CS type of
Scientific paper
10.1007/s10878-011-9405-3
In this paper, we study fractional multiflows in undirected graphs. A fractional multiflow in a graph G with a node subset T, called terminals, is a collection of weighted paths with ends in T such that the total weights of paths traversing each edge does not exceed 1. Well-known fractional path packing problem consists of maximizing the total weight of paths with ends in a subset S of TxT over all fractional multiflows. Together, G,T and S form a network. A network is an Eulerian network if all nodes in N\T have even degrees. A term "fractionality" was defined for the fractional path packing problem by A. Karzanov as the smallest natural number D so that there exists a solution to the problem that becomes integer-valued when multiplied by D. A. Karzanov has defined the class of Eulerian networks in terms of T and S, outside which D is infinite and proved that whithin this class D can be 1,2 or 4. He conjectured that D should be 1 or 2 for this class of networks. In this paper we prove this conjecture.
No associations
LandOfFree
On fractionality of the path packing problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On fractionality of the path packing problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On fractionality of the path packing problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-506763