| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143477 | Operations Research Letters | 2008 | 4 Pages |
Abstract
We study graph orientations that minimize the entropy of the in-degree sequence. We prove that the minimum entropy orientation problem is NP-hard even if the graph is planar, and that there exists a simple linear-time algorithm that returns an approximate solution with an additive error guarantee of 1Â bit.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jean Cardinal, Samuel Fiorini, Gwenaël Joret,