In a distributed system, there could be k indistinguishable shared resources that require exclusive access by different computing nodes. The k-mutual exclusion problem is the problem of guar- anteeing the resource access request in such a way that no more than k computing nodes enter a critical section simultaneously. The use of a k-coterie, which is a special set of node groups, is known as a robust approach to solve this problem. In this paper, we propose a method for constructing optimal k-coteries in terms of availability in general topology networks with unreliable nodes and links. In the proposed method, the problem of constructing an optimal k-coterie is formulated as a 0-1 nonlinear program- ming problem. To solve the formulated problem, we also propose a branch-and-bound method based on a linear programming relax- ation. The feasibility of the proposed method is shown through an experiment conducted for several networks.