"Mathematical Programming and Game Theory", S.K. Neogy, R.B. Bapat, D. Dubey eds., Springer-Verlag (2018), pp.49-66.
Optimization problems on acyclic orientations of graphs, shellability of simplicial complexes, and acyclic partitions.
by Masahiro Hachimori
Abstract
In this paper, we discuss optimization problems on orientations of a given graph, where the values of the objective functions
are determined by the out-degrees of the resulted directed graph and the constraints contain acyclicity of the orientations.
We survey applications of such optimization problems in polytope theory, shellability of simplicial complexes, and acyclic
partitions. We also discuss such optimization problems without acyclicity constraint.