TR-2001-06

On the orientation of graphs and hypergraphs

András Frank, Tamás Király, Zoltán Király

Published in:
Discrete Applied Mathematics 131 (2003), 385-400.



Abstract

In the areas of combinatorial optimization related to submodularity, the uncrossing technique is one of the standard tools for proving min-max relations and integrality results; even its most simple variants have a great diversity of applications. In the present paper we show how standard uncrossing-based methods can lead to new results in the field of graph and hypergraph orientations. The results also include a short proof and an extension of a theorem of Khanna, Naor and Shepherd, and an orientation-type characterization of (2k+1)-edge-connected graphs.


Keywords:
Directed hypergraph, Connectivity, Orientation, Uncrossing


Bibtex entry:

@techreport{egres-01-06,
AUTHOR = {Frank, Andr{\'a}s and Kir{\'a}ly, Tam{\'a}s and Kir{\'a}ly, Zolt{\'a}n},
TITLE = {On the orientation of graphs and hypergraphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-06}
}


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