TR-2010-12

Tree-compositions and submodular flows

András Frank, Csaba Király

Published in:
Operations Research Letters 41:(4) pp. 336-342. (2013)

Tree-compositions were defined in [Frank 1996] to describe the obstacles to k-edge-connected orientability of mixed graphs. Here we describe a structural result on tree-compositions that gives rise to a simple algorithm for computing an obstacle when the orientation does not exists.

• December_2010

Bibtex entry:

@techreport{egres-10-12,

AUTHOR	=	{Frank, Andr{\'a}s and Kir{\'a}ly, Csaba},
TITLE	=	{Tree-compositions and submodular flows},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2010},
NUMBER	=	{TR-2010-12}

}