Minimum Entropy Orientations

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Referees' comments incorporated

Scientific paper

10.1016/j.orl.2008.06.010

We study graph orientations that minimize the entropy of the in-degree sequence. The problem of finding such an orientation is an interesting special case of the minimum entropy set cover problem previously studied by Halperin and Karp [Theoret. Comput. Sci., 2005] and by the current authors [Algorithmica, to appear]. 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. This improves on the only previously known algorithm which has an additive error guarantee of log_2 e bits (approx. 1.4427 bits).

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Minimum Entropy Orientations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Entropy Orientations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Entropy Orientations will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-402670

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.