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)



Abstract

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.


Bibtex entry:

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


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