Publications de l'Institut Mathématique, Nouvelle Série, Vol. 99(113), pp. 99

Publications de l'Institut Mathématique, Nouvelle Série
Vol. 99(113), pp. 99–108 (2016)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

Pick a mirror

A NEW MIXED INTEGER LINEAR PROGRAMMING FORMULATION FOR THE MAXIMUM DEGREE BOUNDED CONNECTED SUBGRAPH PROBLEM

Zoran Maksimovic

Department of Natural Sciences and Mathematics, Military Academy, Belgrade, Serbia

Abstract: 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.

Keywords: integer linear programming; degree-constrained subgraph; combinatorial optimization

Classification (MSC2000): 90C11; 90C27

Full text of the article: (for faster download, first choose a mirror)

Compressed DVI file (24 kilobytes)
Compressed PostScript file (424 kilobytes)
PDF file (168 kilobytes)

Electronic fulltext finalized on: 12 Apr 2016. This page was last modified: 20 Apr 2016.

© 2016 Mathematical Institute of the Serbian Academy of Science and Arts
© 2016 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition