direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints

Degree-constrained orientations of embedded graphs
Zitatschlüssel Report-032-2011
Autor Disser, Yann and Matuschke, Jannik
Jahr 2011
Nummer 032
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We consider the problem of orienting the edges of an embedded graph in such a way that the in-degrees of both the nodes and faces meet given values. We show that if g is the genus of the embedding, the number of feasible solutions is bounded by 4^g and all solutions can be determined within time O(4^g |E|^2 + |E|^3). In particular, for planar graphs the solution is unique if it exists and for every fixed genus there is a polynomial time algorithm to find all solutions. We show that the problem becomes NP-hard if no exact values but only upper and lower bounds on the in-degrees are specified.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag