Szerző dc.contributor.author | Bernáth, Attila | |
Szerző dc.contributor.author | S, Iwata | |
Szerző dc.contributor.author | Király, Tamás | |
Szerző dc.contributor.author | Király, Zoltán | |
Szerző dc.contributor.author | Z, Szigeti | |
Elérhetőség dátuma dc.date.accessioned | 2015-01-06T12:36:38Z | |
Rendelkezésre állás dátuma dc.date.available | 2015-01-06T12:36:38Z | |
Kiadás dc.date.issued | 2008 | |
Issn dc.identifier.issn | 1572-5286 | |
Uri dc.identifier.uri | http://hdl.handle.net/10831/10599 | |
Kivonat dc.description.abstract | 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. | |
Nyelv dc.language | Angol | |
Kapcsolati adatok dc.relation.ispartof | urn:issn:1572-5286 | |
Cím dc.title | Recent results on well-balanced orientations | |
Típus dc.type | folyóiratcikk | |
Változtatás dátuma dc.date.updated | 2014-12-15T16:04:32Z | |
Nyelv dc.language.rfc3066 | eng | |
Megjegyzés dc.description.note | FELTÖLTŐ: Király Tamás - tkiraly@cs.elte.hu FELTÖLTÉSI MEGJEGYZÉS: Technical Report változat | |
Terjedelem dc.format.page | 663-676 | |
Doi azonosító dc.identifier.doi | 10.1016/j.disopt.2008.03.001 | |
Wos azonosító dc.identifier.wos | 000260086600001 | |
Mtmt azonosító dc.identifier.mtmt | 240402 | |
Folyóirat dc.identifier.jtitle | DISCRETE OPTIMIZATION | |
Kötetszám dc.identifier.volume | 5 | |
Kiadás éve dc.description.issuedate | 2008 | |
Szerző szervezeti egysége dc.contributor.institution | Eötvös Loránd Tudományegyetem | |
Szerző intézménye dc.contributor.department | ELTE/ELTE TTK/ELTE TTK MI/MTA-ELTE Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoport | |
Szerző intézménye dc.contributor.department | ELTE/ELTE TTK/ELTE TTK MI/MTA-ELTE Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoport | |
Szerző intézménye dc.contributor.department | ELTE/ELTE TTK/ELTE TTK MI/MTA-ELTE Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoport |
A tételhez tartozó fájlok
Ez a tétel a következő gyűjteményekben található meg
-
Tudományos publikációk (TTK) [3671]