Bidimensionality and Parameterized Algorithms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

Bidimensionality and Parameterized Algorithms

Résumé

We provide an exposition of the main results of the theory of bidimensionality in parameterized algorithm design. This theory applies to graph problems that are bidimensional in the sense that i) their solution value is not increasing when we take minors or contractions of the input graph and ii) their solution value for the (triangulated) (k × k)-grid graph grows as a quadratic function of k. Under certain additional conditions, mainly of logical and combinatorial nature, such problems admit subexponential parameterized algorithms and linear kernels when their inputs are restricted to certain topologically defined graph classes. We provide all formal definitions and concepts in order to present these results in a rigorous way and in their latest update.
Fichier principal
Vignette du fichier
a.pdf (640.9 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01370293 , version 1 (22-09-2016)

Licence

Paternité

Identifiants

Citer

Dimitrios M. Thilikos. Bidimensionality and Parameterized Algorithms. IPEC 2015 - 10th International Symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.1-16, ⟨10.4230/LIPIcs.IPEC.2015.1⟩. ⟨lirmm-01370293⟩
129 Consultations
129 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More