Bidimensionality and Parameterized Algorithms *

Abstract : 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.
Type de document :
Communication dans un congrès
IPEC: International Symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. 10th International Symposium on Parameterized and Exact Computation 43, pp.1-16, 2015, Leibniz International Proceedings in Informatics (LIPIcs). 〈http://algo2015.upatras.gr/ipec/〉. 〈10.4230/LIPIcs.IPEC.2015.1〉
Liste complète des métadonnées

Littérature citée [84 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370293
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 22 septembre 2016 - 12:32:43
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Fichier

a.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Dimitrios M. Thilikos. Bidimensionality and Parameterized Algorithms *. IPEC: International Symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. 10th International Symposium on Parameterized and Exact Computation 43, pp.1-16, 2015, Leibniz International Proceedings in Informatics (LIPIcs). 〈http://algo2015.upatras.gr/ipec/〉. 〈10.4230/LIPIcs.IPEC.2015.1〉. 〈lirmm-01370293〉

Partager

Métriques

Consultations de la notice

71

Téléchargements de fichiers

94