Local improvement algorithms for a path packing problem: A performance analysis based on linear programming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Operations Research Letters Année : 2021

Local improvement algorithms for a path packing problem: A performance analysis based on linear programming

Résumé

Given a graph, we wish to find a maximum number of vertex-disjoint paths of length 2. We propose a series of local improvement algorithms for this problem, and present a linear-programming based method for analyzing their performance.

Domaines

Informatique [cs]
Fichier principal
Vignette du fichier
Local_improvement_algorithms_for_a_path_packing_pr.pdf (399.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Marie-France Sagot  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-03498424

Soumis le : mardi 21 décembre 2021-09:10:12

Dernière modification le : mercredi 15 mars 2023-08:53:38

Archivage à long terme le : mardi 22 mars 2022-19:00:15

Télécharger pour visualiser

Dates et versions

hal-03498424 , version 1 (21-12-2021)

Identifiants

Citer

Koen M J de Bontridder, Bjarni V Halldórsson, Magnús M Halldórsson, Cor a J Hurkens, Jan Karel Lenstra, et al.. Local improvement algorithms for a path packing problem: A performance analysis based on linear programming. Operations Research Letters, 2021, 49 (1), pp.62-68. ⟨10.1016/j.orl.2020.11.005⟩. ⟨hal-03498424⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

INRIA INRIA2
15 Consultations
36 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More