Recherche - Archive ouverte HAL Accéder directement au contenu

Filtrer vos résultats

77 résultats
Page :
triés par

Breaking the $2^n$-barrier for Irredundance: Two lines of attack

 Daniel Binkele-Raible , Ljiljana Brankovic , Marek Cygan , Henning Fernau , Joachim Kneis , et al.
Journal of Discrete Algorithms, 2011, 9 (3), pp.214-230
Article dans une revue hal-00607123v1

Exact exponential algorithms to find tropical connected sets of minimum size

 Mathieu Chapelle , Manfred Cochefert , Dieter Kratsch , Romain Letourneur , Mathieu Liedloff
Theoretical Computer Science, 2017, 676, pp.33-41. ⟨10.1016/j.tcs.2017.03.003⟩
Article dans une revue hal-01971120v1

Guest Editorial: Selected Papers from WG 2014

 Dieter Kratsch , Ioan Todinca
Algorithmica, 2016, 75 (1), pp.186-186. ⟨10.1007/s00453-016-0135-x⟩
Article dans une revue hal-03242344v1

Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In

 Dieter Kratsch , Fedor V. Fomin , Ioan Todinca
2004, pp.568-580
Communication dans un congrès hal-00085561v1

Exact Algorithms for Treewidth and Minimum Fill-In

 Fedor V. Fomin , Dieter Kratsch , Ioan Todinca , Yngve Villanger
SIAM Journal on Computing, 2008, 38 (3), pp.1058-1079. ⟨10.1137/050643350⟩
Article dans une revue hal-00462391v1

End-Vertices of Graph Search Algorithms

 Dieter Kratsch , Mathieu Liedloff , Daniel Meister
9th International Conference CIAC 2015, May 2015, Paris, France. pp.300-312, ⟨10.1007/978-3-319-18173-8_22⟩
Communication dans un congrès hal-01216950v1

Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration

 Jean-François Couturier , Pinar Heggernes , Pim Van’t Hof , Dieter Kratsch
SOFSEM 2012: Theory and Practice of Computer Science, pp.202-213, 2012, ⟨10.1007/978-3-642-27660-6_17⟩
Chapitre d'ouvrage istex hal-02332165v1

Enumerating minimal dominating sets in chordal bipartite graphs

 Petr A. Golovach , Pinar Heggernes , Mamadou Moustapha Kanté , Dieter Kratsch , Yngve Villanger
Discrete Applied Mathematics, 2016, 199, pp.30--36. ⟨10.1016/j.dam.2014.12.010⟩
Article dans une revue hal-02083515v1
Image document

On treewidth approximations

 Vincent Bouchitté , Dieter Kratsch , Haiko Müller , Ioan Todinca
Discrete Applied Mathematics, 2004, 136, pp.183-196
Article dans une revue hal-00085459v1

Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width

 Petr A. Golovach , Pinar Heggernes , Mamadou Moustapha Kanté , Dieter Kratsch , Sigve Sæther , et al.
Algorithmica, 2018, 80, pp.714--741. ⟨10.1007/s00453-017-0289-1⟩
Article dans une revue hal-02083480v1

A linear kernel for finding square roots of almost planar graphs

 Petr Golovach , Dieter Kratsch , Daniël Paulusma , Anthony Stewart
Theoretical Computer Science, 2017, 689, pp.36-47. ⟨10.1016/j.tcs.2017.05.008⟩
Article dans une revue hal-03242340v1

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs

 Petr Golovach , Dieter Kratsch , Mohamed Yosri Sayadi
CIAC 2017: Algorithms and Complexity, pp.297-309, 2017, ⟨10.1007/978-3-319-57586-5_25⟩
Chapitre d'ouvrage hal-03242341v1

Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2

 Petr Golovach , Pinar Heggernes , Dieter Kratsch , Paloma Lima , Daniël Paulusma
WG 2017: Graph-Theoretic Concepts in Computer Science, pp.275-288, 2017, ⟨10.1007/978-3-319-68705-6_21⟩
Chapitre d'ouvrage hal-03242359v1

Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

 Frank von Der Kammer , Dieter Kratsch , Moritz Laudahn
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 2016, Krakow, Poland. pp.56:1--56:14
Communication dans un congrès hal-03242367v1

An exact algorithm for the Maximum Leaf Spanning Tree problem

 Henning Fernau , Joachim Kneis , Dieter Kratsch , Alexander Langer , Mathieu Liedloff , et al.
Theoretical Computer Science, 2011, 412 (45), pp.6290-6302. ⟨10.1016/j.tcs.2011.07.011⟩
Article dans une revue hal-00942908v1

On the parameterized complexity of coloring graphs in the absence of a linear forest

 Jean-François Couturier , Petr A. Golovach , Dieter Kratsch , Daniël Paulusma
Journal of Discrete Algorithms, 2012, 15, pp.56-62. ⟨10.1016/j.jda.2012.04.008⟩
Article dans une revue hal-02332177v1

Faster Algorithms to Enumerate Hypergraph Transversals

 Manfred Cochefert , Jean-François Couturier , Serge Gaspers , Dieter Kratsch
Latin American Symposium on Theoretical Informatics (LATIN), 2016, Ensenada, Mexico. pp.306-318, ⟨10.1007/978-3-662-49529-2_23⟩
Communication dans un congrès hal-02332266v1
Image document

Parameterized Algorithms for Finding Square Roots

 Manfred Cochefert , Jean-François Couturier , Petr A. Golovach , Dieter Kratsch , Daniël Paulusma
2019
Pré-publication, Document de travail hal-02332212v1

Exact exponential-time algorithms for finding bicliques in a graph

 Henning Fernau , Serge Gaspers , Dieter Kratsch , Mathieu Liedloff , Daniel Raible
Proceedings of CTW 2009, 2009, France. pp. 205-209
Communication dans un congrès hal-00943037v1

Exact Algorithms for L(2,1)-Labeling of Graphs

 Frédéric Havet , Martin Klazar , Jan Kratochvil , Dieter Kratsch , Mathieu Liedloff
Algorithmica, 2011, 59 (2), pp.169-194. ⟨10.1007/s00453-009-9302-7⟩
Article dans une revue istex hal-00460873v1

Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size

 Mathieu Chapelle , Manfred Cochefert , Dieter Kratsch , Romain Letourneur , Mathieu Liedloff
Parameterized and Exact Computation - 9th International Symposium, Sep 2014, Wroclaw, Poland. pp.147-158, ⟨10.1007/978-3-319-13524-3_13⟩
Communication dans un congrès hal-01105083v1

Preface: Special graph classes and algorithms–in honor of Professor Andreas Brandstädt on the occasion of his 65th birthday

 Feodor Dragan , Dieter Kratsch , van Bang Le
Discrete Applied Mathematics, 2017, 216, pp.1. ⟨10.1016/j.dam.2016.08.009⟩
Article dans une revue hal-03242339v1

Finding Cactus Roots in Polynomial Time

 Petr Golovach , Dieter Kratsch , Daniël Paulusma , Anthony Stewart
IWOCA 2016: Combinatorial Algorithms, pp.361-372, 2016, ⟨10.1007/978-3-319-44543-4_28⟩
Chapitre d'ouvrage hal-03242352v1

Exact Algorithms for Dominating Set

 Dieter Kratsch
Encyclopedia of Algorithms, Springer New York, pp.667-670, 2016, ⟨10.1007/978-1-4939-2864-4_132⟩
Chapitre d'ouvrage hal-03242354v1
Image document

Exact algorithms for $L(2,1)$-labeling of graphs

 Frédéric Havet , Martin Klazar , Jan Kratochvil , Dieter Kratsch , Matthieu Liedloff
[Research Report] RR-6587, INRIA. 2008
Rapport inria-00303330v1

Matching cut: Kernelization, single-exponential time FPT, and exact exponential algorithms

 Christian Komusiewicz , Dieter Kratsch , van Bang Le
Discrete Applied Mathematics, 2020, 283, pp.44-58. ⟨10.1016/j.dam.2019.12.010⟩
Article dans une revue hal-03242330v1

An Exact Algorithm for the Minimum Dominating Clique Problem

 Dieter Kratsch , Mathieu Liedloff
IWPEC'2006 : 2nd International Workshop on Parameterized and Exact Computation, Sep 2006, Zürich, Switzerland. pp.130-141, ⟨10.1007/11847250_12⟩
Communication dans un congrès istex hal-00460727v1

Exact Algorithms for Weak Roman Domination

 Mathieu Chapelle , Manfred Cochefert , Jean-François Couturier , Dieter Kratsch , Mathieu Liedloff , et al.
IWOCA 2013, Jul 2013, Rouen, France. pp.81-93, ⟨10.1007/978-3-642-45278-9_8⟩
Communication dans un congrès istex hal-00848454v1

Sparse Square Roots

 Manfred Cochefert , Jean-François Couturier , Petr A. Golovach , Dieter Kratsch , Daniël Paulusma
Graph-Theoretic Concepts in Computer Science, pp.177-188, 2013, ⟨10.1007/978-3-642-45043-3_16⟩
Chapitre d'ouvrage hal-02332225v1

Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds

 Petr A. Golovach , Dieter Kratsch , Jean-François Couturier
Graph Theoretic Concepts in Computer Science, pp.39-50, 2010, 978-3-642-16925-0. ⟨10.1007/978-3-642-16926-7_6⟩
Chapitre d'ouvrage istex hal-02332120v1
Page :