Polynomial-time data reduction for dominating set, Journal of the ACM, vol.51, issue.3, pp.363-384, 2004. ,
DOI : 10.1145/990308.990309
URL : http://arxiv.org/abs/cs/0207066
Kernels for the dominating set problem on graphs with an excluded minor, 2008. ,
An algebraic theory of graph reduction, Journal of the ACM, vol.40, issue.5, pp.1134-1164, 1993. ,
DOI : 10.1145/174147.169807
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.3347
Reduction algorithms for constructing solutions in graphs with small treewidth, pp.199-208, 1996. ,
DOI : 10.1007/3-540-61332-3_153
On problems without polynomial kernels, Journal of Computer and System Sciences, vol.75, issue.8, pp.75423-434, 2009. ,
DOI : 10.1016/j.jcss.2009.04.001
URL : http://doi.org/10.1016/j.jcss.2009.04.001
(Meta) Kernelization, Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp.629-638, 2009. ,
DOI : 10.1109/focs.2009.46
URL : https://hal.archives-ouvertes.fr/lirmm-00904532
Reduction Algorithms for Graphs of Small Treewidth, Information and Computation, vol.167, issue.2, pp.86-119, 2001. ,
DOI : 10.1006/inco.2000.2958
Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size, SIAM Journal on Computing, vol.37, issue.4, pp.1077-1106, 2007. ,
DOI : 10.1137/050646354
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.1808
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy, 2012. ,
DOI : 10.1007/978-3-642-40450-4_31
URL : http://arxiv.org/abs/1305.4914
Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs, Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science, pp.147-158, 1997. ,
DOI : 10.1006/jctb.2000.2013
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs, Proceedings of the 42nd ACM Symposium on Theory of Computing, pp.251-26033, 2005. ,
-minor-free graphs, Journal of the ACM, vol.52, issue.6, pp.866-893332, 2005. ,
DOI : 10.1145/1101821.1101823
URL : https://hal.archives-ouvertes.fr/lirmm-00904522
An analogue of the myhill-nerode theorem and its use in computing finite-basis characterizations (extended abstract), FOCS, pp.520-525, 1989. ,
Parameterized Complexity Theory Hitting forbidden minors: Approximation and kernelization Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik Bidimensionality and EPTAS Bidimensionality and geometric graphs, Theoretical Computer Science. An EATCS Series Proceedings of the 8th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), volume 9 of LIPIcs Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011) Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms SIAM, 2012. 22 F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Bidimensionality and kernels Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp.189-200, 2006. ,
Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp.281-309, 2006. ,
DOI : 10.1137/S0097539702419649
26 S. Gutner. Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor Fundamentals of domination in graphs Which problems have strongly exponential complexity?, Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In STOC Proceedings of the 4th Workshop on Parameterized and Exact Computation Lect. Notes Comp. Sc. Linear kernels and single-exponential algorithms via protrusion decompositions. CoRR, abs, pp.173-192, 1207. ,
Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels, Proceedings of the 17th Annual European Symposium on Algorithms, pp.694-70543, 2003. ,
DOI : 10.1007/978-3-642-04128-0_62