Wamiliana, Wamiliana and Syarif, Admi and Junaidi, Akmal and Fitriani, Fitriani (2008) COMB INEQUALITIES FOR THE DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM. Jurnal Sains MIPA, 14 (1). pp. 1-6. ISSN 1978-1873

[img] Text
Comb inequalities for DCMST ....pdf

Download (731kB)


The Degree Constrained Minimum Spanning Tree Problem (DCMST) is a problem of finding the minimum spanning tree in a given wighted graph (all weights are non negative), whilst also satisfies the degree requirement in every vertex. Since the DCMST can be formulated as MILP, then all constraints are valid inequalities, and among those constraints some are facets defining. In this paper we will discuss how to find constraints that constitute comb inequalities for the DCMST for vertex order 5 to 15 with increments 1.

Item Type: Article
Subjects: Q Science > QA Mathematics
Divisions: Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Matematika
Depositing User: Mr. Aang Nuryaman
Date Deposited: 25 Apr 2018 08:01
Last Modified: 25 Apr 2018 08:01
URI: http://repository.lppm.unila.ac.id/id/eprint/6742

Actions (login required)

View Item View Item