A Generalization of the Minimum Branch Vertices Spanning Tree Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2018

A Generalization of the Minimum Branch Vertices Spanning Tree Problem

Abstract

Given a connected graph G = (V, E), a vertex v ∈ V is said to be a branch vertex if d(v) > 2, where d(v) denotes the degree of vertex v. The Minimum Branch Vertices Spanning Tree (MBVST) problem is to nd a spanning tree of G with the minimum number of branch vertices. This problem has been extensively studied in the literature and has welldeveloped applications notably related to routing in optical networks. In this paper, we propose a generalization of this problem, where we begin by introducing the notion of a k-branch vertex, which is a vertex with degree strictly greater than k + 2, and the goal is to determine a spanning tree of G with the minimum number of k-branch vertices (k-MBVST problem). In the context of optical networks, the parameter k can be seen as the limiting capacity of optical splitters to split the input light signal to k sub-trees. Proofs of NP-hardness and non-inclusion in the APX class of the k-MBVST problem are established for a generic value of k, and then an ILP formulation of the k-MBVST problem based on single commodity ow balance constraints is derived. Computational results based on randomly generated graphs show that the number of k-branch vertices included in the spanning tree increases with the size of the vertex set V, but decreases with k as well as graph density. We also show that when k ≥ 4, the number of k-branch vertices in the optimal solution is close to zero, regardless of the size and the density of the underlying graph.
Fichier principal
Vignette du fichier
isco2017_01983084_aG.pdf (327.16 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01888086 , version 1 (16-04-2021)

Identifiers

  • HAL Id : lirmm-01888086 , version 1

Cite

Massinissa Merabet, Jitamitra Desai, Miklós Molnár. A Generalization of the Minimum Branch Vertices Spanning Tree Problem. ROADEF 2018 - 19e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2018, Lorient, France. ⟨lirmm-01888086⟩
90 View
74 Download

Share

Gmail Facebook X LinkedIn More