Recent results on well-balanced orientations

Bernáth, Attila and Iwata, S. and Király, Tamás and Király, Zoltán and Szigeti, Z. (2006) Recent results on well-balanced orientations. Technical Reports. ISSN 1587-4451


Download (424kB) | Preview


In this paper we consider problems related to Nash-Williams' Strong Orientation Theorem and Odd-Vertex Pairing Theorem. These theorems date to 1960 and up to now not much is known about their relationship to other subjects in graph theory. We investigated many approaches to find a more transparent proof for these theorems and possibly generalizations of them. In many cases we found negative answers: counter-examples and NP-completeness results. For example we show that the weighted and the degree-constrained versions of the well-balanced orientation problem are NP-hard. We also show that it is NP-hard to find a minimum cost feasible odd-vertex pairing or to decide whether two graphs with some common edges have simultaneous well-balanced orientations or not. Nash-Williams' original approach was to define best-balanced orientations with feasible odd-vertex pairings: we show here that not every best-balanced orientation can be obtained this way. However we prove that in the global case this is true: every smooth k-arc-connected orientation can be obtained through a k-feasible odd-vertex pairing. The aim of this paper is to help to find a transparent proof for the Strong Orientation Theorem. In order to achieve this we propose some other approaches and raise some open questions, too. (c) 2008 Elsevier B.V. All rights reserved.

Item Type: Article
Additional Information: Published in: DISCRETE OPTIMIZATION (ISSN 1572-5286) 5. évfolyam (2008), 4. szám, p. 663-676. DOI:10.1016/j.disopt.2008.03.001
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 16 Dec 2014 09:42
Last Modified: 16 Dec 2014 09:42

Actions (login required)

Edit Item Edit Item