NP-Completeness, Approximation Results and Mixed Integer Linear Programming Methods for the Minimum Labeling Spanning k-Forest Problem

- 325697
Scientific Initiation Prize - Step 1
Download
Favorite this paper
How to cite this paper?
Abstract

An edge-labeled graph (ELG) is a graph such that each edge has a label associated. Given an ELG G, the minimum labeling spanning k-forest problem consists in finding a spanning forest F of G with minimum number of labels and number of components bounded by k. In this work, a complexity study is realized and an approximation algorithm for the problem is proposed. Continuing on a previous study of a mathematical programming model, we propose two valid inequalities
to reinforce it and analyze computational experiments.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Programme
13:30 to 14:30 on 10/08/2025
Hortensia
Institutions
  • 1 Universidade de São Paulo
  • 2 Universidade Federal do Ceará
Track
  • 16. OD-Discrete Optimization
Keywords
Spanning Forests
Approximation Algorithms
Edge-labeled Graphs