Multicut is FPT - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2011

Multicut is FPT

Nicolas Bousquet
Jean Daligault
  • Fonction : Auteur
  • PersonId : 857844
Stéphan Thomassé

Résumé

Let G=(V,E) be a graph on n vertices and R be a set of pairs of vertices in V called requests. A multicut is a subset F of E such that every request xy of R is cut by F, i.e. every xy-path of G intersects F. We show that there exists an O(f(k)nc) algorithm which decides if there exists a multicut of size at most k. In other words, the Multicut problem parameterized by the solution size k is Fixed-Parameter Tractable.

Dates et versions

lirmm-00741933 , version 1 (15-10-2012)

Identifiants

Citer

Nicolas Bousquet, Jean Daligault, Stéphan Thomassé. Multicut is FPT. STOC 2011 - 43rd Symposium on Theory of Computing, Jun 2011, San José, United States. pp.459-468, ⟨10.1145/1993636.1993698⟩. ⟨lirmm-00741933⟩
140 Consultations
0 Téléchargements

Altmetric

Partager

More