Groupage sur le chemin pour borner la largeur de coupe - IDEX UCA JEDI Université Côte d'Azur Access content directly
Conference Papers Year : 2023

Groupage sur le chemin pour borner la largeur de coupe

Abstract

La largeur de coupe (cutwidth) est un paramètre utilisé dans de nombreux problèmes d'ordonnancement linéaire (layout). Calculer la largeur de coupe est un problème NP-complet, mais il est possible de concevoir des algorithmes de branch-and-bound efficaces si on dispose de bonnes bornes inférieures pour couper des branches lors de l'exploration. Savoir évaluer rapidement de bonnes bornes dans chaque noeud de l'arbre de recherche est donc crucial. Dans cet article, nous donnons de nouvelles bornes basées sur différents paramètres de densité du graphe. Nous donnons aussi une borne inférieure basée sur le groupage de requêtes sur le chemin.
Fichier principal
Vignette du fichier
cutwidth-Algotel.pdf (147.37 Ko) Télécharger le fichier
Origin Files produced by the author(s)
licence

Dates and versions

hal-04076999 , version 1 (21-04-2023)
hal-04076999 , version 2 (26-04-2023)

Licence

Identifiers

  • HAL Id : hal-04076999 , version 2

Cite

Jean-Claude Bermond, Michel Cosnard, David Coudert, Frédéric Havet. Groupage sur le chemin pour borner la largeur de coupe. AlgoTel 2023 - 25èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2023, Cargese, France. pp.4. ⟨hal-04076999v2⟩
78 View
41 Download

Share

Gmail Mastodon Facebook X LinkedIn More