Wamiliana, Wamiliana and Admi Syarif, AS and Junaidi, Akmal and Fitriani, Fitriani (2008) Comb Inequaities for the degree Constrained Minimum Spanning Tree Problem. Jurnal Sains MIPA, 14 (1). pp. 12-16. ISSN 1978-1873

JN_8_JSMIPA_Anggota_2008 - Vol 14_No_1.pdf

Download (1MB) | Preview


The Degree Constrained Minimum Spanning Tree Problem (DCST) is a problem of finding the minimum spanning tree in a given weighted graph (all weights are non negative), whilst also satisfies the degree requirement in every vertex. Since the DOST can be formulated as MLP, 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 constitut e conb inequalities for the DCM ST for vertex order 5 to 15 with increments 1.

Item Type: Article
Subjects: T Technology > T Technology (General)
Divisions: Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Ilmu Komputer
Depositing User: DR Admi Syarif
Date Deposited: 07 Sep 2020 07:59
Last Modified: 07 Sep 2020 07:59
URI: http://repository.lppm.unila.ac.id/id/eprint/23906

Actions (login required)

View Item View Item