Skip to Main content Skip to Navigation
Conference papers

A Generalization of the Minimum Branch Vertices Spanning Tree Problem

Massinissa Merabet 1 Jitamitra Desai 1 Miklós Molnár 2
2 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Conference papers
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01888086
Contributor : Miklos Molnar <>
Submitted on : Friday, April 16, 2021 - 4:22:24 PM
Last modification on : Monday, April 19, 2021 - 10:02:36 AM

File

isco2017_01983084_aG.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01888086, version 1

Collections

Citation

Massinissa Merabet, Jitamitra Desai, Miklós Molnár. A Generalization of the Minimum Branch Vertices Spanning Tree Problem. ROADEF: Recherche Opérationnelle et Aide à la Décision, Feb 2018, Lorient, France. ⟨lirmm-01888086⟩

Share

Metrics

Record views

118

Files downloads

6