An $O(\log \mathrm {OPT})$-Approximation for Covering and Packing Minor Models of $\theta _r$

$An $O(\log \mathrm {OPT})$-Approximation for Covering and Packing Minor Models of $\theta _r$$

Article de revue

Open Access

Avec comité de lecture

Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau et Dimitrios M. Thilikos

Algorithmica, Vol.80(4), pp.1330-1356

04/2018

Résumé

Packings in graphs

Protrusion decomposition

Minor-models of θ

Coverings in graph

Approximation algorithm

Erdős–Pósa property

G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.0: Graph algorithms

url

Find in HALAfficher

url

https://doi.org/10.1007/s00453-017-0313-5Afficher

Published (Version of record) Ouvrir

1 Consultations de la notice

Titre: An $O(\log \mathrm {OPT})$-Approximation for Covering and Packing Minor Models of $\theta _r$
Créateurs - sans rôle: Dimitris Chatzidimitriou - National and Kapodistrian University of Athens
Jean-Florent Raymond - Faculty
Ignasi Sau - Centre National de la Recherche Scientifique
Dimitrios M. Thilikos - Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
Détails de publication: Algorithmica, Vol.80(4), pp.1330-1356
Note de subvention: This research have been supported by the Warsaw Centre of Mathematics and Computer Science (Jean-Florent Raymond), by the (Polish) National Science Centre Grant PRELUDIUM 2013/11/N/ST6/02706 (Jean-Florent Raymond), and by the E.U. (European Social Fund—ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF)—Research Funding Program: “Thales. Investing in knowledge society through the European Social Fund” (Dimitris Chatzidimitriou and Dimitrios M. Thilikos).
Identifiants: 99152650109311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Langue: English
Type de ressource: Journal article
Champs locaux: lirmm-01609998