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
|
Text
Comb inequalities for DCMST ....pdf Download (731kB) | Preview |
Abstract
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 |