Publications 2013 dans le cadre du projet AGAPE

Articles dans des revues internationales

L. Addario-Berry, F. Havet, C. Linhares Sales, B. Reed and S. Thomassé. Oriented trees in digraphs. Discrete Mathematics, 313 (8):967--974, 2013.
J. Araujo, V. Campos, F. Giroire, N. Nisse, L. Sampaio, R. Soares: On the hull number of some graph classes. Theor. Comput. Sci. 475: 1-12, 2013.
S. Bessy and F. Havet. Enumerating the edge-colourings and total colourings of a regular graph. Journal of Combinatorial Optimization, 25(4):523--535, 2013.
S. Bessy and A. Perez. Polynomial kernels for Proper Interval Completion and related problems. Information and Computation, 231:89-108, 2013.
H. Broersma, D. Kratsch, and G. J. Woeginger. Fully decomposable split graphs. Eur. J. Comb. 34(3):567--575, 2013.
J.-F. Couturier, P. A. Golovach, D. Kratsch, M. Liedloff, and A. V. Pyatkin. Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds. Theory Comput. Syst. 52(4):645--667, 2013.
J.-F. Couturier, P. Heggernes, P. van 't Hof, and D. Kratsch. Minimal dominating sets in graph classes: Combinatorial bounds and enumeration. Theor. Comput. Sci. 487:82--94, 2013.
C. Crespelle and I. Todinca: An O(n^2)-time algorithm for the minimal interval completion problem. Theoretical Computer Science 494: 75--85, 2013.
F. V. Fomin, F. Grandoni, D. Kratsch, D. Lokshtanov, and S. Saurabh. Computing Optimal Steiner Trees in Polynomial Space. Algorithmica 65(3):584--604, 2013.
P. A. Golovach, D. Kratsch, D. Paulusma: Detecting induced minors in AT-free graphs. Theor. Comput. Sci. 482:20--32, 2013.
S. Guillemot, F. Havet, C. Paul, and A. Perez. On the (non-)existence of polynomial kernels for P_l-free edge modification problems. Algorithmica, 65(4):900--926, 2013.
K. Junosza-Szaniawski, J. Kratochvíl, M. Liedloff, P. Rossmanith, P. Rzazewski. Fast exact algorithm for L(2, 1)-labeling of graphs. Theoretical Computer Science, 505: 42--54, 2013.
D. Peleg, I. Sau and M. Shalom. On approximating the d-girth of a graph. Discrete Applied Mathematics, 161(16-17):2587--2596, 2013.
J. Rué, I. Sau and D. M. Thilikos. Asymptotic Enumeration of Non-crossing Partitions on Surfaces. Discrete Mathematics, 313(5-6):635--649, 2013.

Proceedings de conférences

L. Blin, J. Burman and N. Nisse: Exclusive Graph Searching. In Proceedings of ESA 2013: 181-192, LNCS 8125, 2013.
M. Chapelle, M. Cochefert, J.-F. Couturier, D. Kratsch, A. Perez, and M. Liedloff. Exact Algorithms for Weak Roman Domination, In Proceedings of IWOCA 2013, to appear.
M. Chapelle, M. Liedloff, I. Todinca and Yngve Villanger. Treewidth and Pathwidth Parameterized by the Vertex Cover Number. In WADS 2013, p. 232--243.
N. Cohen, D. Coudert, and Aurélien Lancin. Algorithme exact et approché pour le calcul de l’hyperbolicité d’un graphe. In 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 1--4, Pornic, France, May 2013.
M. Cochefert, J.-F. Couturier, P. Golovach, D. Kratsch, and D. Paulusma. Sparse square roots. In Proceedings of WG 2013, volume 8165 of LNCS, pages 177--188, 2013.
J.-F. Couturier, M. Liedloff. A tight bound on the number of minimal dominating sets in split graph. In Proceedings of the 12th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), pages 67--70, Enschede, The Netherlands, May 2013.
V. Garnero, I. Sau and D. M. Thilikos. A linear kernel for planar red-blue dominating set. In Proceedings of the 12th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), pages 117--120, Enschede, The Netherlands, May 2013.
F. Giroire, D. Mazauric, N. Nisse, S. Pérennes and R. Soares: Connected Surveillance Game. In Proceedings of SIROCCO 2013: 68-79, LNCS 8179, 2013.
P. A. Golovach, P. Heggernes, D. Kratsch, and A. Rafie. Cliques and Clubs. In CIAC 2013, pages 276--287, Barcelona, Span, May 2013.
P. A. Golovach, P. Heggernes, D. Kratsch, and Y. Villanger. An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), volume 7965 of LNCS, pages 485--496, Riga, Latvia, July 2013.
E. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith, I. Sau and S. Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), volume 7965 of LNCS, pages 613--624, Riga, Latvia, July 2013.
D. Kratsch and S. Kratsch. The jump number problem: exact and parameterized. In Proceedings of IPEC 2013, volume 8246 of LNCS, pages 230 -- 242, 2013.
A. Perez. Linear vertex-kernels for several dense Ranking r-Constraint Satisfaction Problems. TAMC 2013, volume 7876 of LNCS, pages 306-318, 2013.

Rapports de recherches

F. Havet and A. K. Maia, On disjoint directed cycles with prescribed minimum lengths, INRIA Research Report RR-8286, 2013.