  In this paper, we address the scheduling problem in wireless ad hoc networks
by exploiting the computational advantage that comes when such scheduling
problems can be represented by claw-free conflict graphs where we consider a
wireless broadcast medium. It is possible to formulate a scheduling problem of
network coded flows as finding maximum weighted independent set (MWIS) in the
conflict graph of the network. Finding MWIS of a general graph is NP-hard
leading to an NP-hard complexity of scheduling. In a claw-free conflict graph,
MWIS can be found in polynomial time leading to a throughput-optimal
scheduling. We show that the conflict graph of certain wireless ad hoc networks
are claw-free. In order to obtain claw-free conflict graphs in general
networks, we suggest introducing additional conflicts (edges) while keeping the
decrease in MWIS size minimal. To this end, we introduce an iterative
optimization problem to decide where to introduce edges and investigate its
efficient implementation. Besides, we exemplify some physical modifications to
manipulate the conflict graph of a network and also propose a mixed scheduling
strategy for specific networks. We conclude that claw breaking method by adding
extra edges can perform nearly optimal under the necessary assumptions.
