Sandwich problems on orientations
Olivier Durand de Gevigney, Sulamita Klein, Viet-Hang Nguyen, Zoltán Szigeti · Journal of the Brazilian Computer Society · 2012
Abstract The graph sandwich problem for property Π is defined as follows: Given two graphs G 1=(V,E 1) and G 2=(V,E 2) such that E 1⊆E 2, is there a graph G=(V,E) such that E 1⊆E⊆E 2 which satisfies property Π? We propose to study sandwich problems for properties Π concerning orientations, such as Eulerian orientation of a mixed graph and orientation with given in-degrees of a graph. We present a characterization and a polynomial-time algorithm for solving the m-orientation sandwich problem.