Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [84 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370293
Contributor : Dimitrios Thilikos <>
Submitted on : Thursday, September 22, 2016 - 12:32:43 PM
Last modification on : Monday, May 4, 2020 - 9:42:03 AM

File

a.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Dimitrios M. Thilikos. Bidimensionality and Parameterized Algorithms. IPEC: International symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.1-16, ⟨10.4230/LIPIcs.IPEC.2015.1⟩. ⟨lirmm-01370293⟩

Share

Metrics

Record views

159

Files downloads

187