×

zbMATH — the first resource for mathematics

Kratsch, Dieter

Compute Distance To:
Author ID: kratsch.dieter Recent zbMATH articles by "Kratsch, Dieter"
Published as: Kratsch, Dieter; Kratsch, D.
Homepage: http://www.lita.univ-lorraine.fr/~kratsch/
External Links: MGP · Google Scholar · dblp · GND
Documents Indexed: 205 Publications since 1984, including 5 Books
all top 5

Co-Authors

10 single-authored
43 Golovach, Petr A.
32 Müller, Haiko
31 Fomin, Fedor V.
31 Heggernes, Pinar
31 Kloks, Ton
27 Liedloff, Mathieu
17 Paulusma, Daniël
14 Couturier, Jean-Francois
13 Bodlaender, Hans L.
10 Brandstädt, Andreas
9 Cochefert, Manfred
9 Spinrad, Jeremy P.
9 Todinca, Ioan
9 Villanger, Yngve
8 Broersma, Hajo J.
8 Gaspers, Serge
8 Grandoni, Fabrizio
8 Saurabh, Saket
7 Deogun, Jitender S.
6 Kratochvíl, Jan
6 Sayadi, Mohamed Yosri
6 Stewart, Anthony
6 Stewart, Lorna K.
5 Lokshtanov, Daniel
5 Meister, Daniel
4 Chapelle, Mathieu
4 Fernau, Henning
4 Kanté, Mamadou Moustapha
4 Kneis, Joachim
4 Langer, Alexander
4 Lê Văn Băng
4 Rampon, Jean-Xavier
4 Rossmanith, Peter
3 Damaschke, Peter
3 Koster, Arie M. C. A.
3 Kratsch, Stefan
3 Letourneur, Romain
3 Saei, Reza
3 Steiner, George
3 Thilikos, Dimitrios M.
3 Woeginger, Gerhard Johannes
2 Binkele-Raible, Daniel
2 Bouchitté, Vincent
2 Branković, Ljiljana
2 Gimbel, John G.
2 Hemaspaandra, Lane A.
2 Hempel, Harald
2 Huck, Andreas
2 Johnson, Matthew
2 Kammer, Frank
2 Komusiewicz, Christian
2 Koppius, Otto R.
2 Laudahn, Moritz
2 Lehel, Jeno
2 Lima, Paloma T.
2 Liu, Jiping
2 McConnell, Ross M.
2 Mehlhorn, Kurt
2 Novelli, Jean-Christophe
2 Papadopoulos, Charis
2 Patel, Viresh
2 Perez, Anthony
2 Rafiey, Arash
2 Raible, Daniel
2 Raman, Venkatesh
2 Rao, Michaël
2 Sæther, Sigve Hortemo
2 Tuinstra, Hilde
2 van ’t Hof, Pim
1 Babel, Luitpold
1 Bauer, Douglas
1 Chang, Maw-Shang
1 Cohen, Johanne
1 Cygan, Marek
1 Dragan, Feodor F.
1 Erdős, Pál
1 Gyárfás, András
1 Havet, Frédéric
1 Jansen, Klaus
1 Kanj, Iyad A.
1 Katona, Gyula Y.
1 Klazar, Martin
1 Kucherov, Gregory
1 Le Borgne, Yvan
1 Le van, Bang
1 Hoàng-Oanh Le
1 Lee, Chuan-Min
1 Lubiw, Anna
1 Maffray, Frédéric
1 Olariu, Stephan
1 Peng, Sheng-Lung
1 Pilipczuk, Marcin
1 Prisner, Erich
1 Pyatkin, Artem V.
1 Sritharan, R.
1 Timmer, Sjoerd T.
1 Tuza, Zsolt
1 Veldman, Henk Jan
1 Wagner, Dorothea
1 Wojtaszczyk, Jakub Onufry

Publications by Year

Citations contained in zbMATH Open

176 Publications have been cited 1,795 times in 1,167 Documents Cited by Year
Exact exponential algorithms. Zbl 1370.68002
Fomin, Fedor V.; Kratsch, Dieter
131
2010
A measure & conquer approach for the analysis of exact algorithms. Zbl 1325.68311
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
62
2009
Rankings of graphs. Zbl 0907.68137
Bodlaender, Hans L.; Deogun, Jitender S.; Jansen, Klaus; Kloks, Ton; Kratsch, Dieter; Müller, Heiko; Tuza, Zsolt
52
1998
Domination on cocomparability graphs. Zbl 0780.05032
Kratsch, Dieter; Stewart, Lorna
52
1993
Treewidth and pathwidth of permutation graphs. Zbl 0840.05087
Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter
45
1995
Domination in convex and chordal bipartite graphs. Zbl 0706.68055
Damaschke, Peter; Müller, Haiko; Kratsch, Dieter
37
1990
Linear-time certifying recognition algorithms and forbidden induced subgraphs. Zbl 1169.68653
Heggernes, Pinar; Kratsch, Dieter
33
2007
Solving connected dominating set faster than \(2^n\). Zbl 1170.68030
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
33
2008
Measure and conquer: Domination – a case study. Zbl 1082.68866
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
33
2005
On domination problems for permutation and other graphs. Zbl 0641.68100
Brandstädt, Andreas; Kratsch, Dieter
32
1987
Independent sets in asteroidal triple-free graphs. Zbl 0918.68072
Broersma, Hajo; Kloks, Ton; Kratsch, Dieter; Müller, Haiko
29
1999
Certifying algorithms for recognizing interval graphs and permutation graphs. Zbl 1113.68112
Kratsch, Dieter; McConnell, Ross M.; Mehlhorn, Kurt; Spinrad, Jeremy P.
29
2006
Measure and conquer: a simple \(O(2^{0.288n})\) independent set algorithm. Zbl 1192.68960
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
29
2006
Exact algorithms for treewidth and minimum fill-in. Zbl 1163.05320
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve
28
2008
Finding and counting small induced subgraphs efficiently. Zbl 1339.05394
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
28
2000
Listing all minimal separators of a graph. Zbl 0907.68136
Kloks, T.; Kratsch, D.
27
1998
Exact (exponential) algorithms for the dominating set problem. Zbl 1112.68420
Fomin, Fedor V.; Kratsch, Dieter; Woeginger, Gerhard J.
27
2004
On vertex ranking for permutation and other graphs. Zbl 0941.05516
Deogun, J. S.; Kloks, T.; Kratsch, D.; Müller, H.
26
1994
On treewidth and minimum fill-in of asteroidal triple-free graphs. Zbl 0903.68139
Kloks, Ton; Kratsch, Dieter; Spinrad, Jeremy
24
1997
Toughness, hamiltonicity and split graphs. Zbl 0855.05079
Kratsch, Dieter; Lehel, Jenö; Müller, Haiko
24
1996
Approximating the bandwidth for asteroidal triple-free graphs. Zbl 0951.68113
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
24
1999
Some new techniques in design and analysis of exact (exponential) algorithms. Zbl 1169.68669
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
21
2005
Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm. Zbl 0760.05063
Damaschke, Peter; Deogun, Jitender S.; Kratsch, Dieter; Steiner, George
20
1992
Treewidth and minimum fill-in on \(d\)-trapezoid graphs. Zbl 0905.68101
Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter; Müller, Haiko
20
1998
Additive tree spanners. Zbl 1041.05024
Kratsch, Dieter; Le, Hoàng-Oanh; Müller, Haiko; Prisner, Erich; Wagner, Dorothea
19
2003
Some extremal results in cochromatic and dichromatic theory. Zbl 0743.05047
Erdős, Paul; Gimbel, John; Kratsch, Dieter
18
1991
On the structure of (\(P_{5}\), gem)-free graphs. Zbl 1084.05048
Brandstädt, Andreas; Kratsch, Dieter
17
2005
Bandwidth of chain graphs. Zbl 1339.05393
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
17
1998
Minimal dominating sets in graph classes: combinatorial bounds and enumeration. Zbl 1283.05200
Couturier, Jean-François; Heggernes, Pinar; van ’t Hof, Pim; Kratsch, Dieter
16
2013
On the vertex ranking problem for trapezoid, circular-arc and other graphs. Zbl 0937.68093
Deogun, Jitender S.; Kloks, Ton; Kratsch, Dieter; Müller, Haiko
15
1999
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1213.68455
Havet, Frédéric; Klazar, Martin; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
15
2011
A note on exact algorithms for vertex ordering problems on graphs. Zbl 1253.68164
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
15
2012
Measuring the vulnerability for classes of intersection graphs. Zbl 0881.05118
Kratsch, Dieter; Kloks, Ton; Müller, Haiko
14
1997
Efficient algorithms for graphs with few \(P_4\)’s. Zbl 0980.05045
Babel, Luitpold; Kloks, Ton; Kratochvil, Jan; Kratsch, Dieter; Müller, Haiko; Olariu, Stephan
14
2001
Domination and total domination on asteroidal triple-free graphs. Zbl 0943.05063
Kratsch, Dieter
14
2000
Certifying algorithms for recognizing interval graphs and permutation graphs. Zbl 1094.68615
Kratsch, Dieter; McConnell, Ross M.; Mehlhorn, Kurt; Spinrad, Jeremy P.
14
2003
On algorithms for (\(P_5\), gem)-free graphs. Zbl 1086.68050
Bodlaender, Hans L.; Brandstädt, Andreas; Kratsch, Dieter; Rao, Michaël; Spinrad, Jeremy
14
2005
On independent sets and bicliques in graphs. Zbl 1202.05096
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
14
2008
Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack. Zbl 1225.05227
Binkele-Raible, Daniel; Brankovic, Ljiljana; Cygan, Marek; Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Pilipczuk, Marcin; Rossmanith, Peter; Wojtaszczyk, Jakub Onufry
14
2011
On exact algorithms for Treewidth. Zbl 1301.05328
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
14
2012
1-tough cocomparability graphs are hamiltonian. Zbl 0876.05066
Deogun, Jitender S.; Kratsch, Dieter; Steiner, George
13
1997
Minimum fill-in on circle and circular-arc graphs. Zbl 0912.68156
Kloks, T.; Kratsch, D.; Wong, C. K.
13
1998
Treewidth of chordal bipartite graphs. Zbl 0839.68070
Kloks, T.; Kratsch, D.
13
1995
Exact (exponential) algorithms for treewidth and minimum fill-in. Zbl 1099.68076
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan
13
2004
On exact algorithms for treewidth. Zbl 1131.68481
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
13
2006
On cocolourings and cochromatic numbers of graphs. Zbl 0795.05052
Gimbel, John; Kratsch, Dieter; Stewart, Lorna
12
1994
Exact algorithms for graph homomorphisms. Zbl 1119.68133
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter
12
2007
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
12
2016
Approximating minimum cocolorings. Zbl 1042.68091
Fomin, Fedor V.; Kratsch, Dieter; Novelli, Jean-Christophe
11
2002
Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph. Zbl 0875.68458
Kloks, T.; Kratsch, D.
11
1995
On treewidth approximations. Zbl 1035.05087
Bouchitté, V.; Kratsch, D.; Müller, H.; Todinca, I.
11
2004
Towards the reconstruction of posets. Zbl 0819.06002
Kratsch, Dieter; Rampon, Jean-Xavier
10
1994
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs. Zbl 0729.05046
Kratsch, Dieter
10
1990
Convex recoloring revisited: complexity and exact algorithms. Zbl 1248.05201
Kanj, Iyad A.; Kratsch, Dieter
10
2009
On the recognition of probe graphs of some self-complementary classes of perfect graphs. Zbl 1128.05313
Chang, Maw-Shang; Kloks, Ton; Kratsch, Dieter; Liu, Jiping; Peng, Sheng-Lung
10
2005
Enumerating minimal subset feedback vertex sets. Zbl 1303.05189
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter; Papadopoulos, Charis; Villanger, Yngve
10
2014
On partitions of permutations into increasing and decreasing subsequences. Zbl 0616.05002
Brandstädt, Andreas; Kratsch, Dieter
9
1986
Asteroidal sets in graphs. Zbl 0897.05076
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
9
1997
On the structure of graphs with bounded asteroidal number. Zbl 0989.05059
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
9
2001
Dominating cliques in chordal graphs. Zbl 0796.05052
Kratsch, Dieter; Damaschke, Peter; Lubiw, Anna
9
1994
Minimal fill in O(\(n^{2.69}\)) time. Zbl 1084.05070
Kratsch, Dieter; Spinrad, Jeremy
9
2006
Optimal linear arrangement of interval graphs. Zbl 1132.68501
Cohen, Johanne; Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Kucherov, Gregory
9
2006
Feedback vertex set on AT-free graphs. Zbl 1152.68044
Kratsch, Dieter; Müller, Haiko; Todinca, Ioan
9
2008
Faster Steiner tree computation in polynomial-space. Zbl 1158.68429
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
9
2008
Bandwidth of bipartite permutation graphs in polynomial time. Zbl 1209.05242
Heggernes, Pinar; Kratsch, Dieter; Meister, Daniel
9
2009
Iterative compression and exact algorithms. Zbl 1186.68187
Fomin, Fedor V.; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket
9
2010
An exact algorithm for the maximum leaf spanning tree problem. Zbl 1233.68236
Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Raible, Daniel; Rossmanith, Peter
9
2011
On independent sets and bicliques in graphs. Zbl 1239.05101
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
9
2012
Total domination and transformation. Zbl 1337.68133
Kratsch, Dieter; Stewart, Lorna
9
1997
Subset feedback vertex sets in chordal graphs. Zbl 1298.05302
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
9
2014
Parameterized algorithms for finding square roots. Zbl 1332.05136
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
9
2016
On claw-free asteroidal triple-free graphs. Zbl 1002.68109
Hempel, Harald; Kratsch, Dieter
8
2002
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1147.05310
Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
8
2007
Kayles and Numbers. Zbl 1005.68112
Bodlaender, Hans L.; Kratsch, Dieter
7
2002
Approximating bandwidth by mixing layouts of interval graphs. Zbl 1006.05052
Kratsch, D.; Stewart, L.
7
2002
Bandwidth of split and circular permutation graphs. Zbl 0988.68125
Kloks, Ton; Kratsch, Dieter; Le Borgne, Yvan; Müller, Haiko
7
2000
List coloring in the absence of a linear forest. Zbl 1305.05073
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
7
2011
Enumerating minimal connected dominating sets in graphs of bounded chordality. Zbl 1339.05190
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
7
2016
Finding clubs in graph classes. Zbl 1298.05092
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash
7
2014
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1330.05118
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
7
2015
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
Exponential time algorithms for the minimum dominating set problem on some graph classes. Zbl 1300.05300
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Todinca, Ioan
7
2009
Enumerating minimal dominating sets in chordal bipartite graphs. Zbl 1326.05105
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve
7
2016
Algorithms. Zbl 0896.05054
Kratsch, Dieter
6
1998
On the complexity of graph reconstruction. Zbl 0806.05051
Kratsch, Dieter; Hemaspaandra, Lane A.
6
1994
Finding all minimal separators of a graph. Zbl 0941.05514
Kloks, T.; Kratsch, D.
6
1994
A generalization of AT-free graphs and a generic algorithm for solving triangulation problems. Zbl 1009.68099
Broersma, H. J.; Kloks, T.; Kratsch, D.; Müller, H.
6
2002
An exact algorithm for the minimum dominating clique problem. Zbl 1125.68135
Kratsch, Dieter; Liedloff, Mathieu
6
2007
An exact algorithm for the maximum leaf spanning tree problem. Zbl 1273.05219
Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Raible, Daniel; Rossmanith, Peter
6
2009
Sparse square roots. Zbl 1331.05204
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
6
2013
An approximation algorithm for clustering graphs with dominating diametral path. Zbl 1337.68290
Deogun, Jitender S.; Kratsch, Dieter; Steiner, George
6
1997
Space-efficient biconnected components and recognition of outerplanar graphs. Zbl 1398.05201
Kammer, Frank; Kratsch, Dieter; Laudahn, Moritz
6
2016
Computing optimal Steiner trees in polynomial space. Zbl 1269.05049
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter; Lokshtanov, Daniel; Saurabh, Saket
6
2013
Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Zbl 1383.05162
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve H.; Villanger, Yngve
6
2018
Finding the minimum bandwidth of an interval graph. Zbl 0621.68042
Kratsch, Dieter
5
1987
A counterexample about poset reconstruction. Zbl 0806.06003
Kratsch, Dieter; Rampon, Jean-Xavier
5
1994
Chordality and 2-factors in tough graphs. Zbl 0937.68094
Bauer, D.; Katona, G. Y.; Kratsch, D.; Veldman, H. J.
5
2000
Degree-preserving trees. Zbl 0938.90065
Broersma, Hajo; Koppius, Otto; Tuinstra, Hilde; Huck, Andreas; Kloks, Ton; Kratsch, Dieter; Müller, Haiko
5
2000
Exponential time algorithms for the minimum dominating set problem on some graph classes. Zbl 1141.68529
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
5
2006
Feedback vertex set and longest induced path on AT-free graphs. Zbl 1255.05188
Kratsch, Dieter; Müller, Haiko; Todinca, Ioan
5
2003
Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms. Zbl 1442.05224
Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang
2
2020
Enumeration of maximal irredundant sets for claw-free graphs. Zbl 1409.05109
Golovach, Petr A.; Kratsch, Dieter; Sayadi, Mohamed Yosri
2
2019
Enumeration and maximum number of maximal irredundant sets for chordal graphs. Zbl 1416.05267
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
1
2019
Enumeration and maximum number of minimal dominating sets for chordal graphs. Zbl 1428.05139
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
1
2019
Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Zbl 1383.05162
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve H.; Villanger, Yngve
6
2018
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 1373.05008
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
3
2018
Computing square roots of graphs with low maximum degree. Zbl 1395.05083
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
3
2018
Finding cactus roots in polynomial time. Zbl 1391.68052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
2
2018
Exact algorithms for weak Roman domination. Zbl 1395.05168
Chapelle, Mathieu; Cochefert, Manfred; Couturier, Jean-Fraņcois; Kratsch, Dieter; Letourneur, Romain; Liedloff, Mathieu; Perez, Anthony
1
2018
Minimal dominating sets in interval graphs and trees. Zbl 1350.05121
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Villanger, Yngve
3
2017
A linear kernel for finding square roots of almost planar graphs. Zbl 1372.05052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
3
2017
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Zbl 1421.68081
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Lima, Paloma T.; Paulusma, Daniël
2
2017
Enumeration and maximum number of maximal irredundant sets for chordal graphs. Zbl 06822006
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
1
2017
Enumeration of maximal irredundant sets for claw-free graphs. Zbl 1441.05015
Golovach, Petr A.; Kratsch, Dieter; Sayadi, Mohamed Yosri
1
2017
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
12
2016
Parameterized algorithms for finding square roots. Zbl 1332.05136
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
9
2016
Enumerating minimal connected dominating sets in graphs of bounded chordality. Zbl 1339.05190
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
7
2016
Enumerating minimal dominating sets in chordal bipartite graphs. Zbl 1326.05105
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve
7
2016
Space-efficient biconnected components and recognition of outerplanar graphs. Zbl 1398.05201
Kammer, Frank; Kratsch, Dieter; Laudahn, Moritz
6
2016
Algorithms solving the matching cut problem. Zbl 1331.68109
Kratsch, Dieter; Le, Van Bang
5
2016
A linear kernel for finding square roots of almost planar graphs. Zbl 1378.68077
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Squares of low clique number. Zbl 1356.05102
Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Finding cactus roots in polynomial time. Zbl 1391.68051
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 06562488
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
3
2016
Faster algorithms to enumerate hypergraph transversals. Zbl 06576677
Cochefert, Manfred; Couturier, Jean-François; Gaspers, Serge; Kratsch, Dieter
1
2016
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1330.05118
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
7
2015
List coloring in the absence of a linear forest. Zbl 1307.05068
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
5
2015
Exact algorithms for Kayles. Zbl 1305.05143
Bodlaender, Hans L.; Kratsch, Dieter; Timmer, Sjoerd T.
1
2015
Algorithms solving the matching cut problem. Zbl 1459.68159
Kratsch, Dieter; Le, Van Bang
1
2015
End-vertices of graph search algorithms. Zbl 1459.68160
Kratsch, Dieter; Liedloff, Mathieu; Meister, Daniel
1
2015
Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Zbl 1382.05033
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve H.; Villanger, Yngve
1
2015
Enumerating minimal subset feedback vertex sets. Zbl 1303.05189
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter; Papadopoulos, Charis; Villanger, Yngve
10
2014
Subset feedback vertex sets in chordal graphs. Zbl 1298.05302
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
9
2014
Finding clubs in graph classes. Zbl 1298.05092
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash
7
2014
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
Exact exponential algorithms to find a tropical connected set of minimum size. Zbl 1456.68228
Chapelle, Mathieu; Cochefert, Manfred; Kratsch, Dieter; Letourneur, Romain; Liedloff, Mathieu
1
2014
Minimal dominating sets in graph classes: combinatorial bounds and enumeration. Zbl 1283.05200
Couturier, Jean-François; Heggernes, Pinar; van ’t Hof, Pim; Kratsch, Dieter
16
2013
Sparse square roots. Zbl 1331.05204
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
6
2013
Computing optimal Steiner trees in polynomial space. Zbl 1269.05049
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter; Lokshtanov, Daniel; Saurabh, Saket
6
2013
Detecting induced minors in AT-free graphs. Zbl 1296.05183
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
3
2013
Fully decomposable split graphs. Zbl 1257.05125
Broersma, Hajo; Kratsch, Dieter; Woeginger, Gerhard J.
3
2013
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1336.05133
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
2
2013
Exact algorithms for weak Roman domination. Zbl 1408.68112
Chapelle, Mathieu; Cochefert, Manfred; Couturier, Jean-François; Kratsch, Dieter; Liedloff, Mathieu; Perez, Anthony
2
2013
Colorings with few colors: counting, enumeration and combinatorial bounds. Zbl 1269.05034
Couturier, Jean-Francois; Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Pyatkin, Artem
1
2013
Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization. Zbl 1358.68313
Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket
1
2013
A note on exact algorithms for vertex ordering problems on graphs. Zbl 1253.68164
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
15
2012
On exact algorithms for Treewidth. Zbl 1301.05328
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
14
2012
On independent sets and bicliques in graphs. Zbl 1239.05101
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
9
2012
Colouring AT-free graphs. Zbl 1365.68287
Kratsch, Dieter; Müller, Haiko
3
2012
Minimal dominating sets in graph classes: combinatorial bounds and enumeration. Zbl 1298.05246
Couturier, Jean-François; Heggernes, Pinar; van’t Hof, Pim; Kratsch, Dieter
3
2012
An exact algorithm for subset feedback vertex set on chordal graphs. Zbl 1374.05216
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
3
2012
On the parameterized complexity of coloring graphs in the absence of a linear forest. Zbl 1247.68108
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
2
2012
Bicolored independent sets and bicliques. Zbl 1243.68185
Couturier, Jean-François; Kratsch, Dieter
1
2012
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1213.68455
Havet, Frédéric; Klazar, Martin; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
15
2011
Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack. Zbl 1225.05227
Binkele-Raible, Daniel; Brankovic, Ljiljana; Cygan, Marek; Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Pilipczuk, Marcin; Rossmanith, Peter; Wojtaszczyk, Jakub Onufry
14
2011
An exact algorithm for the maximum leaf spanning tree problem. Zbl 1233.68236
Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Raible, Daniel; Rossmanith, Peter
9
2011
List coloring in the absence of a linear forest. Zbl 1305.05073
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
7
2011
Enumerating minimal subset feedback vertex sets. Zbl 1342.68162
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter; Papadopoulos, Charis; Villanger, Yngve
4
2011
Bandwidth on AT-free graphs. Zbl 1228.68036
Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket
3
2011
Exact algorithms for Kayles. Zbl 1339.05251
Bodlaender, Hans L.; Kratsch, Dieter
2
2011
Exact exponential algorithms. Zbl 1370.68002
Fomin, Fedor V.; Kratsch, Dieter
131
2010
Iterative compression and exact algorithms. Zbl 1186.68187
Fomin, Fedor V.; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket
9
2010
Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing. Zbl 1285.68207
Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket
5
2010
Parameterized algorithm for eternal vertex cover. Zbl 1234.68150
Fomin, Fedor V.; Gaspers, Serge; Golovach, Petr A.; Kratsch, Dieter; Saurabh, Saket
5
2010
Colorings with few colors: counting, enumeration and combinatorial bounds. Zbl 1309.05172
Golovach, Petr A.; Kratsch, Dieter; Couturier, Jean-Francois
2
2010
A parameterized route to exact puzzles: breaking the \(2^{n }\)-barrier for irredundance (extended abstract). Zbl 1284.05266
Binkele-Raible, Daniel; Brankovic, Ljiljana; Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Rossmanith, Peter
2
2010
A measure & conquer approach for the analysis of exact algorithms. Zbl 1325.68311
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
62
2009
Convex recoloring revisited: complexity and exact algorithms. Zbl 1248.05201
Kanj, Iyad A.; Kratsch, Dieter
10
2009
Bandwidth of bipartite permutation graphs in polynomial time. Zbl 1209.05242
Heggernes, Pinar; Kratsch, Dieter; Meister, Daniel
9
2009
Exponential time algorithms for the minimum dominating set problem on some graph classes. Zbl 1300.05300
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Todinca, Ioan
7
2009
An exact algorithm for the maximum leaf spanning tree problem. Zbl 1273.05219
Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Raible, Daniel; Rossmanith, Peter
6
2009
Sort and Search: exact algorithms for generalized domination. Zbl 1197.05104
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
3
2009
Bandwidth on AT-free graphs. Zbl 1272.05199
Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket
2
2009
On a property of minimal triangulations. Zbl 1205.05122
Kratsch, Dieter; Müller, Haiko
2
2009
Fully decomposable split graphs. Zbl 1267.05245
Broersma, Hajo; Kratsch, Dieter; Woeginger, Gerhard J.
1
2009
Solving connected dominating set faster than \(2^n\). Zbl 1170.68030
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
33
2008
Exact algorithms for treewidth and minimum fill-in. Zbl 1163.05320
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve
28
2008
On independent sets and bicliques in graphs. Zbl 1202.05096
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
14
2008
Feedback vertex set on AT-free graphs. Zbl 1152.68044
Kratsch, Dieter; Müller, Haiko; Todinca, Ioan
9
2008
Faster Steiner tree computation in polynomial-space. Zbl 1158.68429
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
9
2008
Iterative compression and exact algorithms. Zbl 1173.68537
Fomin, Fedor V.; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket
3
2008
Bandwidth of bipartite permutation graphs in polynomial time. Zbl 1136.05323
Heggernes, Pinar; Kratsch, Dieter; Meister, Daniel
1
2008
A new characterization of HH-free graphs. Zbl 1226.05238
Kratsch, Dieter; Spinrad, Jeremy P.; Sritharan, R.
1
2008
Linear-time certifying recognition algorithms and forbidden induced subgraphs. Zbl 1169.68653
Heggernes, Pinar; Kratsch, Dieter
33
2007
Exact algorithms for graph homomorphisms. Zbl 1119.68133
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter
12
2007
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1147.05310
Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
8
2007
An exact algorithm for the minimum dominating clique problem. Zbl 1125.68135
Kratsch, Dieter; Liedloff, Mathieu
6
2007
Branch and recharge: exact algorithms for generalized domination. Zbl 1209.05240
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
1
2007
Certifying algorithms for recognizing interval graphs and permutation graphs. Zbl 1113.68112
Kratsch, Dieter; McConnell, Ross M.; Mehlhorn, Kurt; Spinrad, Jeremy P.
29
2006
Measure and conquer: a simple \(O(2^{0.288n})\) independent set algorithm. Zbl 1192.68960
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
29
2006
On exact algorithms for treewidth. Zbl 1131.68481
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
13
2006
Minimal fill in O(\(n^{2.69}\)) time. Zbl 1084.05070
Kratsch, Dieter; Spinrad, Jeremy
9
2006
Optimal linear arrangement of interval graphs. Zbl 1132.68501
Cohen, Johanne; Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Kucherov, Gregory
9
2006
Exponential time algorithms for the minimum dominating set problem on some graph classes. Zbl 1141.68529
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
5
2006
Solving connected dominating set faster than \(2^{n}\). Zbl 1170.68545
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
4
2006
Between \(O(nm)\) and \(O(n^{\alpha})\). Zbl 1115.05086
Kratsch, Dieter; Spinrad, Jeremy
2
2006
Improved bottleneck domination algorithms. Zbl 1104.68129
Kloks, Ton; Kratsch, Dieter; Lee, Chuan-Min; Liu, Jiping
1
2006
Measure and conquer: Domination – a case study. Zbl 1082.68866
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
33
2005
Some new techniques in design and analysis of exact (exponential) algorithms. Zbl 1169.68669
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
21
2005
On the structure of (\(P_{5}\), gem)-free graphs. Zbl 1084.05048
Brandstädt, Andreas; Kratsch, Dieter
17
2005
...and 76 more Documents
all top 5

Cited by 1,431 Authors

82 Kratsch, Dieter
40 Golovach, Petr A.
39 Heggernes, Pinar
38 Paulusma, Daniël
35 Fomin, Fedor V.
33 Liedloff, Mathieu
28 Saurabh, Saket
24 Bodlaender, Hans L.
23 Fernau, Henning
19 Villanger, Yngve
19 Xiao, Mingyu
18 Lokshtanov, Daniel
18 Lozin, Vadim Vladislavovich
17 Chang, Maw-Shang
17 Dragan, Feodor F.
17 Todinca, Ioan
16 Gaspers, Serge
16 Kloks, Ton
16 Müller, Haiko
16 Paschos, Vangelis Th.
15 Papadopoulos, Charis
14 Ekim, Tınaz
14 Raman, Venkatesh
13 Brandstädt, Andreas
12 Dabrowski, Konrad Kazimierz
12 Köhler, Ekkehard
12 Rossmanith, Peter
12 Rzążewski, Paweł
11 Della Croce, Federico
11 Komusiewicz, Christian
11 Mosca, Raffaele
11 Otachi, Yota
11 Stewart, Lorna K.
10 Broersma, Hajo J.
10 Couturier, Jean-Francois
10 Cygan, Marek
10 Habib, Michel A.
10 Meister, Daniel
10 Niedermeier, Rolf
10 Pilipczuk, Michał
9 Chen, Li-Hsuan
9 Corneil, Derek Gordon
9 Milanič, Martin
9 Nagamochi, Hiroshi
9 Nešetřil, Jaroslav
9 Ono, Hirotaka
9 Panda, Bhawani Sankar
9 Pilipczuk, Marcin
9 Sampaio, Rudini Menezes
9 Szwarcfiter, Jayme Luiz
9 Thilikos, Dimitrios M.
8 Berry, Anne
8 Binkele-Raible, Daniel
8 de Figueiredo, Celina M. Herrera
8 Escoffier, Bruno
8 Gimbel, John G.
8 Junosza-Szaniawski, Konstanty
8 Kanté, Mamadou Moustapha
8 Kratochvíl, Jan
8 Lê Văn Băng
8 Lingas, Andrzej
8 Nikolopoulos, Stavros D.
8 Peng, Sheng-Lung
8 Uehara, Ryuhei
8 Uno, Takeaki
8 van ’t Hof, Pim
7 Bazgan, Cristina
7 Hung, Ling-Ju
7 Hung, Ruowei
7 Mertzios, George B.
7 Narayan, Darren A.
7 Nisse, Nicolas
7 Ossona de Mendez, Patrice
7 Rampon, Jean-Xavier
7 van Rooij, Johan M. M.
7 Wakabayashi, Yoshiko
6 Bourgeois, Nicolas
6 Branković, Ljiljana
6 Campos, Victor A.
6 Chang, Gerard Jennhwa
6 Chen, Genhuey
6 Damaschke, Peter
6 Giannopoulou, Archontia C.
6 Grandoni, Fabrizio
6 Johnson, Matthew
6 Kowalik, Łukasz
6 Kowaluk, Mirosław
6 Lin, Min Chih
6 Misra, Neeldhara
6 Nishimura, Naomi
6 Saitoh, Toshiki
6 Stacho, Juraj
6 Steiner, George
6 T’kindt, Vincent
5 Bauer, Douglas
5 Belmonte, Rémy
5 Bonsma, Paul S.
5 Bouchitté, Vincent
5 Chandran, L. Sunil
5 Chaplick, Steven
...and 1,331 more Authors
all top 5

Cited in 107 Serials

231 Discrete Applied Mathematics
161 Theoretical Computer Science
93 Algorithmica
73 Information Processing Letters
69 Discrete Mathematics
27 Journal of Combinatorial Optimization
22 Journal of Discrete Algorithms
21 Theory of Computing Systems
18 Journal of Computer and System Sciences
18 SIAM Journal on Discrete Mathematics
12 European Journal of Combinatorics
11 Graphs and Combinatorics
10 Journal of Graph Theory
10 European Journal of Operational Research
10 Discrete Mathematics, Algorithms and Applications
8 Information Sciences
8 Order
8 Information and Computation
8 International Journal of Foundations of Computer Science
8 Discrete Optimization
8 Algorithms
7 Networks
7 Annals of Operations Research
7 International Journal of Computer Mathematics
7 The Electronic Journal of Combinatorics
7 Journal of Graph Algorithms and Applications
6 Journal of Combinatorial Theory. Series B
6 Computers & Operations Research
6 Discussiones Mathematicae. Graph Theory
5 Artificial Intelligence
5 Mathematical Programming. Series A. Series B
5 Optimization Letters
4 RAIRO. Operations Research
4 AKCE International Journal of Graphs and Combinatorics
3 Acta Informatica
3 SIAM Journal on Computing
3 INFORMS Journal on Computing
3 Acta Universitatis Sapientiae. Informatica
3 Prikladnaya Diskretnaya Matematika
2 Applied Mathematics and Computation
2 BIT
2 Computing
2 International Journal of Game Theory
2 Journal of Combinatorial Theory. Series A
2 Journal of Automated Reasoning
2 International Journal of Approximate Reasoning
2 Computational Geometry
2 Linear Algebra and its Applications
2 Computational Complexity
2 Journal of Scheduling
2 Annals of Combinatorics
2 Journal of Discrete Mathematical Sciences & Cryptography
2 Logical Methods in Computer Science
2 Computer Science Review
1 Journal of Mathematical Biology
1 Rocky Mountain Journal of Mathematics
1 Geometriae Dedicata
1 International Journal of Mathematics and Mathematical Sciences
1 Journal of the American Statistical Association
1 Journal of Computational and Applied Mathematics
1 Operations Research
1 Transactions of the American Mathematical Society
1 Advances in Applied Mathematics
1 Operations Research Letters
1 Combinatorica
1 Optimization
1 Discrete & Computational Geometry
1 Applied Mathematics Letters
1 Random Structures & Algorithms
1 Discrete Mathematics and Applications
1 Computational Statistics
1 Aequationes Mathematicae
1 Applied Mathematical Modelling
1 Communications in Statistics. Theory and Methods
1 Distributed Computing
1 Cybernetics and Systems Analysis
1 Computational Optimization and Applications
1 Journal of Computer and Systems Sciences International
1 Journal of Mathematical Sciences (New York)
1 The Journal of Artificial Intelligence Research (JAIR)
1 Annals of Mathematics and Artificial Intelligence
1 Journal of Heuristics
1 Mathematical Problems in Engineering
1 Vietnam Journal of Mathematics
1 Soft Computing
1 Mathematical Methods of Operations Research
1 Journal of the ACM
1 Discrete Mathematics and Theoretical Computer Science. DMTCS
1 RAIRO. Theoretical Informatics and Applications
1 CEJOR. Central European Journal of Operations Research
1 Trudy Instituta Matematiki
1 Bulletin of the Malaysian Mathematical Sciences Society. Second Series
1 Comptes Rendus. Mathématique. Académie des Sciences, Paris
1 Quantum Information Processing
1 4OR
1 ACM Journal of Experimental Algorithmics
1 Internet Mathematics
1 Mathematics in Computer Science
1 Networks and Heterogeneous Media
1 Operational Research. An International Journal
...and 7 more Serials

Citations by Year