Geometry and algorithms for alpha-orientations
Abstract: Given a graph G=(V,E) and a function alpha:V->N, an orientation D of G is an alpha-orientation if for all v in V the outdegree of v in D is alpha(v). Alpha-orientations model a variety of graph objects, form vertices of a polytope, and can be transformed into each other by simple flip operations. We study different notions of distance between alpha-orientations and determine the complexity of their computation. Moreover, we design efficient enumeration algorithms for alpha-orientations and feasible alpha-vectors. As an application we obtain simple enumeration algorithms for k-connected orientations.