Solving the minimum labeling global cut problem by mathematical programming

التفاصيل البيبلوغرافية
العنوان:	Solving the minimum labeling global cut problem by mathematical programming
المؤلفون:	Koehler, Victor, Gouveia, Thiago, Sousa Filho, Gilberto Farias De, Ochi, Luiz Satoru, Michelon, Philippe, Gueye, Serigne, Cabral, Lucidio
المساهمون:	Laboratoire Informatique d'Avignon (LIA), Avignon Université (AU)-Centre d'Enseignement et de Recherche en Informatique - CERI
المصدر:	ISSN: 0969-6016.
بيانات النشر:	HAL CCSD Wiley
سنة النشر:	2024
المجموعة:	Université d'Avignon et des Pays de Vaucluse: HAL
مصطلحات موضوعية:	[INFO.INFO-RO]Computer Science [cs]/Operations Research [math.OC]
الوصف:	International audience ; Abstract An edge‐labeled graph (ELG) is a graph such that is the set of vertices, is the set of edges, is the set of labels (colors), and each edge has a label associated. Given an ELG , the goal of the minimum labeling global cut problem (MLGCP) is to find a subset such that the removal of all edges with labels in disconnects and is minimum. This work proposes three new mathematical formulations for the MLGCP, namely PART , VC , and TE as well as branch‐and‐cut algorithms to solve them. Additionally, a theoretical study was carried out on the MLGCP input graph, leading to the concept of chromatic closure, used in preprocessing algorithms for this model PART . Finally, a comprehensive polyhedral investigation of the model is performed. The computational experiments showed that the model, adopting the chromatic closure concept and its branch‐and‐cut algorithm, can solve small to average‐sized instances in reasonable times.
نوع الوثيقة:	article in journal/newspaper
اللغة:	English
Relation:	info:eu-repo/semantics/altIdentifier/arxiv/1903.04319; ARXIV: 1903.04319
DOI:	10.1111/itor.13571
الاتاحة:	https://hal.science/hal-04787936 https://doi.org/10.1111/itor.13571
رقم الانضمام:	edsbas.4CCA4B1
قاعدة البيانات:	BASE

View record in BASE

الوصف
DOI:	10.1111/itor.13571