Combinatorial optimization-based methods are widely used to solve complex real life problems. In this thesis, we use some of these methods for addressing several emerging combinatorial opti- mization problems on graphs ...