Publications
Réunions
Problèmes
Participants
PmWiki
pmwiki.org
edit SideBar
|
Publications 2010 dans le cadre du projet AGAPE
Livre
- F.V. Fomin and D. Kratsch, Exact Exponential Algorithms, Texts in Computer Science, An EATCS Series, Hardcover, 204 p., Springer, 2010.
Articles dans des revues internationales
- S. Bessy, C. Paul, and A. Perez. Polynomial kernels for 3-leaf power graph modification problems. Discrete Applied Mathematics 158:1732-1744, 2010.
- D. Binkele-Raible, H. Fernau, S. Gaspers, and M. Liedloff. Exact exponential-time algorithms for finding bicliques. Information Processing Letters 111: 64-67, 2010.
- N. Cohen and F. Havet. Planar graphs with maximum degree $\Delta\geq 9$ are ($\Delta+1$)-edge-choosable -- short proof. Discrete Mathematics, 310(21):3049-3051, 2010. fichier PDF
- J. Daligault, M. Rao, and S. Thomassé. Well-quasi-order of relabel functions. Order 27:301-315, 2010.
- J. Daligault, D. Gonçalves, and M. Rao, Diamond-free circle graphs are Helly circle. Discrete Math. 310(4):845-849, 2010.
- J. Daligault, G. Gutin, E.-J. Kim, and A. Yeo. FPT algorithms and kernels for the Directed k-Leaf Problem. J. Comput. Syst. Sci. 76:144-152, 2010.
- N. Eggemann, F. Havet, and S. Noble. k-L(2,1)-Labelling for Planar Graphs is NP-Complete for $k\geq 4$. Discrete Applied Mathematics 158(16): 1777-1788, 2010. fichier PDF
- F. Fomin, S. Gaspers, D. Kratsch, M. Liedloff and S. Saurabh, Iterative compression and exact algorithms.Theoretical Computer Science 411: 1045-1053, 2010.
- F. Fomin, S. Gaspers, P. Golovach, D. Kratsch, and S. Saurabh. Parameterized algorithm for eternal vertex cover, Information Processing Letters 110: 702-706, 2010.
- F. Fomin, P. Golovach, J. Kratochvil, N. Nisse, and K. Suchan. Pursuing a fast robber on a graph. Theoretical Computer Science 411(7-9): 1167-1181, 2010. fichier PDF
- L. Lyaudet, F. Mazoit, and S. Thomassé. Partitions versus sets: A case of duality. European J. Combin. 31:681-687, 2010.
- I. Sau and D. M. Thilikos. Subexponential Parameterized Algorithms for Degree-constrained Subgraph Problems on Planar Graphs. Journal of Discrete Algorithms, 8(3):330--338, 2010. fichier PDF
- J.-C. Bermond, C. J. Colbourn, L. Gionfriddo, G. Quattrocchi and I. Sau. Drop Cost and Wavelength Optimal Two-Period Grooming with Ratio 4. SIAM Journal on Discrete Mathematics, 24(2): 400--419, 2010.
- S. Thomassé. A quadratic kernel for feedback vertex set. ACM Transactions on Algorithms', 6, Art. 32, 8 pp., 2010.
Proceedings de conférences
- I. Adler, F. Dorn, F. V. Fomin, I. Sau, and D. M. Thilikos. Faster Parameterized Algorithms for Minor Containment. Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Springer-Verlag, 2010, Berlin, LNCS 6139, pp. 322-333.
- I. Adler, F. Dorn, F. V. Fomin, I. Sau, and D. M. Thilikos. Fast Minor Testing in Planar Graphs. Proceedings of the 18th Annual European Symposium on Algorithms (ESA), Springer-Verlag, 2010, Berlin, LNCS 6346, pp. 97-109.
- D. Binkele-Raible, L. Brankovic, H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, and P. Rossmanith. Breaking the $2^n$-barrier for irredundance: a parameterized route to solving exact puzzles, Proceedings of CIAC 2010, Springer-Verlag, 2010, Berlin, LNCS 6078, pp. 311-322.
- N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno and N. Nisse. Tradeoffs in process strategy games with application in the WDM reconfiguration problem. Fifth International conference on Fun with Algorithms (FUN 2010), Springer-Verlag, 2010, Berlin, LNCS 6099, pp. 121-132, 2010. fichier PDF
- C. Crespelle and I. Todinca: An $O(n^2){\mathcal{O}}(n^2)$-time Algorithm for the Minimal Interval Completion Problem. ``Porccedings of TAMC 2010'', pp. 175--186, 2010.
- M. Fellows, P. Giannopoulos, C. Knauer, C. Paul, F. Rosamond, S. Whitesides and N. Yu. Milling a graph with turn costs : a parameterized complexity perspective. Graph Theoretical Concepts in Computer Science - WG , Springer-Verlag, 2010, Berlin, LNCS 6410, pp. 123-134.
- P.A. Golovach, D. Kratsch, and J.F. Couturier. Colorings with few colors: counting, enumeration and combinatorial bounds.``Proceedings of WG 2010'', Springer-Verlag, 2010, Berlin, LNCS 6410, pp. 39--50.
- G. Gutin, E.-J. Kim, A. Soleimanfallah, S. Szeider, and A. Yeo. Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming. International Symposium on Parameterized and Exact Computation(IPEC), Springer-Verlag, 2010, Berlin, LNCS 6478.
- S. Guillemot, C. Paul and A. Perez. On the (non-)existence of polynomial kernels for Pl-free edge modification problems. International Symposium on Parameterized and Exact Computation(IPEC), Springer-Verlag, 2010, Berlin, LNCS 6478.
- F. Havet and L. Sampaio. On the Grundy number of a graph. International Symposium on Parameterized and Exact Computation(IPEC), Springer-Verlag, 2010, Berlin, LNCS 6478.
- N. Hanusse, D. Ilcinkas, A. Kosowski, and N. Nisse. Locating a target with an agent guided by unreliable local advice. In Proceedings of 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 355-364, 2010. fichier PDF
- P. Heggernes, D. Kratsch, D. Lokshtanov, V. Raman, and S. Saurabh. Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Proceedings of SWAT 2010}, Springer-Verlag, 2010, Berlin, LNCS 6139, pp. 334-345.
- F. Huc, C. Caillouet, N. Nisse, S. Pérennes and H. Rivano. Stability of a localized and greedy routing algorithm. 12th Workshop on Advances in Parallel and Distributed Computational Models, IEEE, to appear, 2010. fichier PDF
- C. Lenté, M. Liedloff, E. Neron, A. Soukhal et V. T'Kindt. Complexité d'algorithmes exponentiels : application au domaine de l'ordonnancement. ROADEF'2010 : 11ième congrès de la Société Francaise de Recherche Opérationnelle et d'Aide à la Décision. Toulouse, France. 2010.
- M. Liedloff, I. Todinca,and Y. Villanger. Solving Capacitated dominating Set by using Covering by Subsets and Maximum Matching. Proceedings of WG 2010, Springer-Verlag, 2010, Berlin, LNCS 6410, pp. 88-99.
- J. Rué, I. Sau, and D. M. Thilikos. Dynamic Programming for Graphs on Surfaces. Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Springer-Verlag, 2010, Berlin, LNCS 6198, pp. 372-383.
Rapports de recherches
- J. Bang-Jensen, F. Havet, and N. Trotignon. Finding an induced subdivision of a digraph INRIA Research Report RR-7430, Oct. 2010. fichier PDF
- J. Chalopin, V. Chepoi, N. Nisse and Y. Vaxès. Cop and robber games when the robber can hide and ride. INRIA Research Report RR-7178, Jan. 2010. fichier PDF
- V. Campos, A. Gyárfás, F. Havet, C. Linhares Sales and F. Maffray. New bounds on the Grundy number of products of graphs. INRIA Research Report RR-7243, Apr. 2010. fichier PDF
- N. Hanusse, D. Ilcinkas, A. Kosowski and N. Nisse. How to beat the random walk when you have a clock? INRIA Research Report RR-7210, Feb. 2010. fichier PDF
- F. Havet, C. Linhares Sales and L. Sampaio. b-coloring of tight graphs. INRIA Research Report RR-7241, Mar. 2010. fichier PDF
- J. Daligault, C. Paul, A. Perez and S. Thomassé. Reducing Multicut to bounded treewidth. submitted.
|