TR-2008-12

Strongly polynomial time solvability of integral and half-integral node-capacitated multiflow problems

Gyula Pap

We show the strongly polynomial time solvability of the problem of finding a maximum half-integral node-capacitated multiflow, and of the problem of finding a maximum integral node-capacitated multiflow.

Bibtex entry:

@techreport{egres-08-12,

AUTHOR	=	{Pap, Gyula},
TITLE	=	{Strongly polynomial time solvability of integral and half-integral node-capacitated multiflow problems},
NOTE	=	{{\tt www.cs.elte.hu/egres}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2008},
NUMBER	=	{TR-2008-12}

}