Minimum entropy orientations

Minimum entropy orientations

0.00 Avg rating0 Votes
Article ID: iaor20102900
Volume: 36
Issue: 6
Start Page Number: 680
End Page Number: 683
Publication Date: Nov 2008
Journal: Operations Research Letters
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.