Local improvement algorithms for a path packing problem: A performance analysis based on linear programming - Archive ouverte HAL Access content directly
Journal Articles Operations Research Letters Year : 2021

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

(1) , (2) , (2) , (3) , (4) , (5) , (4, 6)
1
2
3
4
5
6

Abstract

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.
Fichier principal
Vignette du fichier
Local_improvement_algorithms_for_a_path_packing_pr.pdf (399.82 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

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⟩

Collections

INRIA INRIA2
17 View
32 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More