A New Mixed Integer Linear Programming Formulation for the Maximum Degree Bounded Connected Subgraph Problem


Zoran Maksimović




In this paper is given a new mixed integer linear programming (MILP) formulation for Maximum Degree Bounded Connected Subgraph Problem (MDBCSP). The proposed MILP formulation is the first in literature with polynomial number of constraints. Therefore, it will be possible to solve optimally much more instances then before in a reasonable time.