Eulerian orientations and circulations. (English) Zbl 0576.05046
Authors’ abstract: ”Let \(G=(V,E)\) be an (undirected) Eulerian graph. An Eulerian orientation \(\vec G\) of G is a directed graph obtained by giving each edge of G an orientation in such a way that \(\vec G\) contains a directed Eulerian tour. If each edge [u,v] of G has real costs c(u,v) and c(v,u) associated with it, depending on which way it is oriented, then the cost of an Eulerian orientation \(\vec G\) is the sum of the costs of its arcs. We show how the problem of finding a minimum cost Eulerian orientation can be transformed into a minimum cost circulation problem. We also describe direct algorithms for the minimum cost Eulerian orientation problem which can be viewed as specializations of general network flow algorithms for the transformed problem. The orientation graph \(\theta\) (G) has a node for every Eulerian orientation, and the nodes corresponding to \(\vec G\) and \(\tilde G\) are adjacent in \(\theta\) (G) if and only if \(\vec G\) and \(\tilde G\) differ only for the edges belonging to a simple cycle C of G. (Necessarily, the corresponding arcs will comprise directed cycles in \(\vec G\) and \(\tilde G.\)) We show that \(\theta\) (G) is either isomorphic to a d-dimensional hypercube for some d or else is Hamilton connected (i.e. each pair of nodes is joined by a Hamiltonian path of \(\theta\) (G)).”
Reviewer: M.C.Heydemann
MSC:
05C45 | Eulerian and Hamiltonian graphs |
05C20 | Directed graphs (digraphs), tournaments |
90B10 | Deterministic network models in operations research |
References:
[1] | Frank, András, On the orientation of graphs, J. Combin. Theory Ser. B, 28, 251, (1980) · Zbl 0443.05045 |
[2] | Frank, András, An algorithm for submodular functions on graphs, Bonn Workshop on Combinatorial Optimization (Bonn, 1980), 16, 97, (1982), North-Holland, Amsterdam · Zbl 0504.05059 |
[3] | Frank, András, A note on {\it k}-strongly connected orientations of an undirected graph, Discrete Math., 39, 103, (1982) · Zbl 0481.05030 · doi:10.1016/0012-365X(82)90044-9 |
[4] | On the windy postman problemCORR Report83-6Dept. Combinatorics and Optimization, Univ. WaterlooWaterloo, Ontario, Canada |
[5] | Lawler, EugeneL., Combinatorial optimization: networks and matroids, (1976) · Zbl 0413.90040 |
[6] | Naddef, D.; Pulleyblank, W. R., Hamiltonicity and combinatorial polyhedra, J. Combin. Theory Ser. B, 31, 297, (1981) · Zbl 0449.05042 |
[7] | Naddef, D. J.; Pulleyblank, W. R., Hamiltonicity in \((0- 1)\)-polyhedra, J. Combin. Theory Ser. B, 37, 41, (1984) · Zbl 0544.05058 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.