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.

Older versions:

Bibtex entry:

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

Last modification: 6.4.2021. Please email your comments to Tamás Király!