Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am not even sure of how to search for an answer to this, or how to approach the problem myself, so I thought I would try to ask it here.

Consider an n-vertex hypergraph where the vertices are numbered from 1 to n. Each edge is given a "score" based on the lowest numbered vertex it contains.

Is it possible to efficiently renumber the vertices in a way that maximizes the sum of all the edge scores?

I'm not really seeing any way to do this short of the naive method of trying every permutation. I'd appreciate a shove in the right direction.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.