The minimum-weight ideal problem for signed posets

The minimum-weight ideal problem for signed posets

0.00 Avg rating0 Votes
Article ID: iaor19972543
Country: Japan
Volume: 39
Issue: 4
Start Page Number: 558
End Page Number: 565
Publication Date: Dec 1996
Journal: Journal of the Operations Research Society of Japan
Authors: , ,
Keywords: networks, optimization
Abstract:

The concept of signed poset has recently been introduced by V. Reiner as a generalization of that of ordinary poset (partially ordered set). The authors consider the problem of finding a minimum-weight ideal of a signed poset. They show a representation theorem that there exists a bijection between the set of all the ideals of a signed poset and the set of all the ‘reduced ideals’ (defined here) of the associated ordinary poset, which was earlier proved by S. D. Fischer. It follows from this representation theorem that the minimum-weight ideal problem for a signed poset can be reduced to a problem of finding a minimum-weight (reduced) ideal of the associated ordinary poset and hence to a minimum-cut problem. The authors also consider the case when the weight of an ideal is defined in terms of two weight functions. The problem is also reduced to a minimum-cut problem by the same reduction technique as above. Furthermore, the relationship between the minimum-weight ideal problem and a certain bisubmodular function minimization problem is revealed.

Reviews

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