出版社：Japan Science and Technology Information Aggregator, Electronic
摘要：In this note, we consider the uncrossing game for a skew-supermodular function f , hich is a two-player game with players, Red and Blue, and abstracts the uncrossing procedure in the cut-covering linear program associated with f . Extending the earlier results by Karzanov for {0,1}-valued skew-supermodular functions, we present an improved polynomial time strategy for Red to win, and give a strongly polynomial time uncrossing procedure for dual solutions of the cut-covering LP as its consequence. We also mention its implication on the optimality of laminar solutions.
