×
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
all top 5

Co-Authors

10 single-authored
44 Golovach, Petr A.
36 Müller, Haiko
35 Kloks, Ton
31 Fomin, Fedor V.
31 Heggernes, Pinar
27 Liedloff, Mathieu
17 Paulusma, Daniël
14 Bodlaender, Hans L.
14 Couturier, Jean-Francois
10 Brandstädt, Andreas
9 Cochefert, Manfred
9 Deogun, Jitender S.
9 Spinrad, Jeremy P.
9 Todinca, Ioan
9 Villanger, Yngve
8 Broersma, Hajo J.
8 Gaspers, Serge
8 Grandoni, Fabrizio
8 Saurabh, Saket
6 Kratochvíl, Jan
6 Lê Văn Băng
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 Rampon, Jean-Xavier
4 Rossmanith, Peter
3 Damaschke, Peter
3 Komusiewicz, Christian
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
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 Jansen, Klaus
2 Johnson, Matthew
2 Kammer, Frank
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 Tuza, Zsolt
2 van ’t Hof, Pim
2 Wong, Chak-Kuen
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 Kanj, Iyad A.
1 Katona, Gyula Y.
1 Klazar, Martin
1 Kucherov, Gregory
1 Le Borgne, Yvan
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 L.
1 Prisner, Erich
1 Pyatkin, Artëm Valer’evich
1 Sritharan, R.
1 Timmer, Sjoerd T.
1 Veldman, Henk Jan
1 Wagner, Dorothea
1 Wojtaszczyk, Jakub Onufry

Publications by Year

Citations contained in zbMATH Open

188 Publications have been cited 2,347 times in 1,553 Documents Cited by Year
Exact exponential algorithms. Zbl 1370.68002
Fomin, Fedor V.; Kratsch, Dieter
191
2010
A measure & conquer approach for the analysis of exact algorithms. Zbl 1325.68311
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
82
2009
Domination on cocomparability graphs. Zbl 0780.05032
Kratsch, Dieter; Stewart, Lorna
68
1993
Rankings of graphs. Zbl 0907.68137
Bodlaender, Hans L.; Deogun, Jitender S.; Jansen, Klaus; Kloks, Ton; Kratsch, Dieter; Müller, Heiko; Tuza, Zsolt
65
1998
Linear-time certifying recognition algorithms and forbidden induced subgraphs. Zbl 1169.68653
Heggernes, Pinar; Kratsch, Dieter
55
2007
Treewidth and pathwidth of permutation graphs. Zbl 0840.05087
Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter
51
1995
Domination in convex and chordal bipartite graphs. Zbl 0706.68055
Damaschke, Peter; Müller, Haiko; Kratsch, Dieter
46
1990
Finding and counting small induced subgraphs efficiently. Zbl 1339.05394
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
46
2000
Measure and conquer: Domination – a case study. Zbl 1082.68866
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
39
2005
Solving connected dominating set faster than \(2^n\). Zbl 1170.68030
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
38
2008
Certifying algorithms for recognizing interval graphs and permutation graphs. Zbl 1113.68112
Kratsch, Dieter; McConnell, Ross M.; Mehlhorn, Kurt; Spinrad, Jeremy P.
36
2006
Exact (exponential) algorithms for the dominating set problem. Zbl 1112.68420
Fomin, Fedor V.; Kratsch, Dieter; Woeginger, Gerhard J.
35
2004
On domination problems for permutation and other graphs. Zbl 0641.68100
Brandstädt, Andreas; Kratsch, Dieter
34
1987
Toughness, hamiltonicity and split graphs. Zbl 0855.05079
Kratsch, Dieter; Lehel, Jenö; Müller, Haiko
34
1996
Exact algorithms for treewidth and minimum fill-in. Zbl 1163.05320
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve
34
2008
Measure and conquer: a simple \(O(2^{0.288n})\) independent set algorithm. Zbl 1192.68960
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
34
2006
Independent sets in asteroidal triple-free graphs. Zbl 0918.68072
Broersma, Hajo; Kloks, Ton; Kratsch, Dieter; Müller, Haiko
32
1999
Listing all minimal separators of a graph. Zbl 0907.68136
Kloks, T.; Kratsch, D.
31
1998
On vertex ranking for permutation and other graphs. Zbl 0941.05516
Deogun, J. S.; Kloks, T.; Kratsch, D.; Müller, H.
30
1994
On treewidth and minimum fill-in of asteroidal triple-free graphs. Zbl 0903.68139
Kloks, Ton; Kratsch, Dieter; Spinrad, Jeremy
27
1997
Approximating the bandwidth for asteroidal triple-free graphs. Zbl 0951.68113
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
26
1999
Treewidth and minimum fill-in on \(d\)-trapezoid graphs. Zbl 0905.68101
Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter; Müller, Haiko
26
1998
Some new techniques in design and analysis of exact (exponential) algorithms. Zbl 1169.68669
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
23
2005
On the structure of (\(P_{5}\),gem)-free graphs. Zbl 1084.05048
Brandstädt, Andreas; Kratsch, Dieter
23
2005
Some extremal results in cochromatic and dichromatic theory. Zbl 0743.05047
Erdős, Paul; Gimbel, John; Kratsch, Dieter
23
1991
Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm. Zbl 0760.05063
Damaschke, Peter; Deogun, Jitender S.; Kratsch, Dieter; Steiner, George
23
1992
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
22
1999
Enumerating minimal subset feedback vertex sets. Zbl 1303.05189
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter; Papadopoulos, Charis; Villanger, Yngve
22
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
22
2013
Measuring the vulnerability for classes of intersection graphs. Zbl 0881.05118
Kratsch, Dieter; Kloks, Ton; Müller, Haiko
21
1997
Domination and total domination on asteroidal triple-free graphs. Zbl 0943.05063
Kratsch, Dieter
20
2000
Additive tree spanners. Zbl 1041.05024
Kratsch, Dieter; Le, Hoàng-Oanh; Müller, Haiko; Prisner, Erich; Wagner, Dorothea
20
2003
1-tough cocomparability graphs are hamiltonian. Zbl 0876.05066
Deogun, Jitender S.; Kratsch, Dieter; Steiner, George
20
1997
Bandwidth of chain graphs. Zbl 1339.05393
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
20
1998
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.
19
2012
Certifying algorithms for recognizing interval graphs and permutation graphs. Zbl 1094.68615
Kratsch, Dieter; McConnell, Ross M.; Mehlhorn, Kurt; Spinrad, Jeremy P.
18
2003
On exact algorithms for treewidth. Zbl 1131.68481
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
17
2006
List coloring in the absence of a linear forest. Zbl 1307.05068
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
17
2015
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
17
2016
Optimal linear arrangement of interval graphs. Zbl 1132.68501
Cohen, Johanne; Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Kucherov, Gregory
16
2006
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
16
2011
Minimum fill-in on circle and circular-arc graphs. Zbl 0912.68156
Kloks, T.; Kratsch, D.; Wong, C. K.
16
1998
Exact (exponential) algorithms for treewidth and minimum fill-in. Zbl 1099.68076
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan
16
2004
On exact algorithms for Treewidth. Zbl 1301.05328
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
16
2012
Subset feedback vertex sets in chordal graphs. Zbl 1298.05302
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
16
2014
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
Treewidth of chordal bipartite graphs. Zbl 0839.68070
Kloks, T.; Kratsch, D.
15
1995
On algorithms for (\(P_5\), gem)-free graphs. Zbl 1086.68050
Bodlaender, Hans L.; Brandstädt, Andreas; Kratsch, Dieter; Rao, Michaël; Spinrad, Jeremy
15
2005
On independent sets and bicliques in graphs. Zbl 1202.05096
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
15
2008
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1330.05118
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
15
2015
Algorithms solving the matching cut problem. Zbl 1331.68109
Kratsch, Dieter; Le, Van Bang
15
2016
On independent sets and bicliques in graphs. Zbl 1239.05101
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
14
2012
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
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
14
2005
Exact algorithms for graph homomorphisms. Zbl 1119.68133
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter
13
2007
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs. Zbl 0729.05046
Kratsch, Dieter
13
1990
Convex recoloring revisited: complexity and exact algorithms. Zbl 1248.05201
Kanj, Iyad A.; Kratsch, Dieter
13
2009
Enumerating minimal dominating sets in chordal bipartite graphs. Zbl 1326.05105
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve
13
2016
Parameterized algorithm for eternal vertex cover. Zbl 1234.68150
Fomin, Fedor V.; Gaspers, Serge; Golovach, Petr A.; Kratsch, Dieter; Saurabh, Saket
12
2010
Iterative compression and exact algorithms. Zbl 1186.68187
Fomin, Fedor V.; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket
12
2010
On partitions of permutations into increasing and decreasing subsequences. Zbl 0616.05002
Brandstädt, Andreas; Kratsch, Dieter
12
1986
On cocolourings and cochromatic numbers of graphs. Zbl 0795.05052
Gimbel, John; Kratsch, Dieter; Stewart, Lorna
12
1994
Dominating cliques in chordal graphs. Zbl 0796.05052
Kratsch, Dieter; Damaschke, Peter; Lubiw, Anna
12
1994
Feedback vertex set on AT-free graphs. Zbl 1152.68044
Kratsch, Dieter; Müller, Haiko; Todinca, Ioan
12
2008
Approximating minimum cocolorings. Zbl 1042.68091
Fomin, Fedor V.; Kratsch, Dieter; Novelli, Jean-Christophe
12
2002
Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms. Zbl 1442.05224
Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang
12
2020
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
11
2018
On the structure of graphs with bounded asteroidal number. Zbl 0989.05059
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
11
2001
On treewidth approximations. Zbl 1035.05087
Bouchitté, V.; Kratsch, D.; Müller, H.; Todinca, I.
11
2004
On the restriction of some NP-complete graph problems to permutation graphs. Zbl 0575.68069
Brandstädt, Andreas; Kratsch, Dieter
11
1985
Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph. Zbl 0875.68458
Kloks, T.; Kratsch, D.
11
1995
Finding clubs in graph classes. Zbl 1298.05092
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash
11
2014
Towards the reconstruction of posets. Zbl 0819.06002
Kratsch, Dieter; Rampon, Jean-Xavier
10
1994
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
10
2011
Bandwidth of bipartite permutation graphs in polynomial time. Zbl 1209.05242
Heggernes, Pinar; Kratsch, Dieter; Meister, Daniel
10
2009
Asteroidal sets in graphs. Zbl 0897.05076
Kloks, Ton; Kratsch, Dieter; Müller, Haiko
10
1997
Parameterized algorithms for finding square roots. Zbl 1332.05136
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
10
2016
Faster Steiner tree computation in polynomial-space. Zbl 1158.68429
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
10
2008
Feedback vertex set and longest induced path on AT-free graphs. Zbl 1255.05188
Kratsch, Dieter; Müller, Haiko; Todinca, Ioan
9
2003
Minimal fill in O(\(n^{2.69}\)) time. Zbl 1084.05070
Kratsch, Dieter; Spinrad, Jeremy
9
2006
Total domination and transformation. Zbl 1337.68133
Kratsch, Dieter; Stewart, Lorna
9
1997
Exponential time algorithms for the minimum dominating set problem on some graph classes. Zbl 1300.05300
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Todinca, Ioan
9
2009
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1147.05310
Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
9
2007
On claw-free asteroidal triple-free graphs. Zbl 1002.68109
Hempel, Harald; Kratsch, Dieter
9
2002
Kayles and Numbers. Zbl 1005.68112
Bodlaender, Hans L.; Kratsch, Dieter
9
2002
Approximating the bandwidth for asteroidal triple-free graphs. Zbl 1512.68235
Kloks, T.; Kratsch, D.; Müller, H.
9
1995
Between \(O(nm)\) and \(O(n^{\alpha})\). Zbl 1115.05086
Kratsch, Dieter; Spinrad, Jeremy
8
2006
Chordality and 2-factors in tough graphs. Zbl 0937.68094
Bauer, D.; Katona, G. Y.; Kratsch, D.; Veldman, H. J.
8
2000
Degree-preserving trees. Zbl 0938.90065
Broersma, Hajo; Koppius, Otto; Tuinstra, Hilde; Huck, Andreas; Kloks, Ton; Kratsch, Dieter; Müller, Haiko
8
2000
Bandwidth of split and circular permutation graphs. Zbl 0988.68125
Kloks, Ton; Kratsch, Dieter; Le Borgne, Yvan; Müller, Haiko
8
2000
Enumerating minimal connected dominating sets in graphs of bounded chordality. Zbl 1339.05190
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
8
2016
Approximating bandwidth by mixing layouts of interval graphs. Zbl 1006.05052
Kratsch, D.; Stewart, L.
8
2002
Finding all minimal separators of a graph. Zbl 0941.05514
Kloks, T.; Kratsch, D.
7
1994
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
An exact algorithm for the minimum dominating clique problem. Zbl 1125.68135
Kratsch, Dieter; Liedloff, Mathieu
7
2007
Space-efficient biconnected components and recognition of outerplanar graphs. Zbl 1398.05201
Kammer, Frank; Kratsch, Dieter; Laudahn, Moritz
7
2016
On the complexity of graph reconstruction. Zbl 0806.05051
Kratsch, Dieter; Hemaspaandra, Lane A.
7
1994
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
Sparse square roots. Zbl 1331.05204
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
7
2013
Solving connected dominating set faster than \(2^{n}\). Zbl 1170.68545
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
6
2006
Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. Zbl 1479.68002
Golovach, Petr A.; Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang
5
2022
Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms. Zbl 1442.05224
Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang
12
2020
Enumeration of minimal connected dominating sets for chordal graphs. Zbl 1437.05104
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
3
2020
Space-efficient biconnected components and recognition of outerplanar graphs. Zbl 1444.68077
Kammer, Frank; Kratsch, Dieter; Laudahn, Moritz
3
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
3
2019
Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms. Zbl 1516.68067
Komusiewicz, Christian; Kratsch, Dieter; Van Bang Le
2
2019
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
2
2019
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Zbl 1421.68082
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Lima, Paloma T.; Paulusma, Daniël
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
11
2018
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 1373.05008
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
6
2018
Finding cactus roots in polynomial time. Zbl 1391.68052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
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
4
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
2
2018
Minimal dominating sets in interval graphs and trees. Zbl 1350.05121
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Villanger, Yngve
6
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
4
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 1483.05180
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
1
2017
Exact exponential algorithms to find tropical connected sets of minimum size. Zbl 1369.05190
Chapelle, Mathieu; Cochefert, Manfred; Kratsch, Dieter; Letourneur, Romain; Liedloff, Mathieu
1
2017
Enumeration of maximal irredundant sets for claw-free graphs. Zbl 1441.05015
Golovach, Petr A.; Kratsch, Dieter; Sayadi, Mohamed Yosri
1
2017
Enumerating minimal tropical connected sets. Zbl 1450.05041
Kratsch, Dieter; Liedloff, Mathieu; 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
17
2016
Algorithms solving the matching cut problem. Zbl 1331.68109
Kratsch, Dieter; Le, Van Bang
15
2016
Enumerating minimal dominating sets in chordal bipartite graphs. Zbl 1326.05105
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve
13
2016
Parameterized algorithms for finding square roots. Zbl 1332.05136
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
10
2016
Enumerating minimal connected dominating sets in graphs of bounded chordality. Zbl 1339.05190
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
8
2016
Space-efficient biconnected components and recognition of outerplanar graphs. Zbl 1398.05201
Kammer, Frank; Kratsch, Dieter; Laudahn, Moritz
7
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 1476.68208
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
3
2016
Faster algorithms to enumerate hypergraph transversals. Zbl 1475.68474
Cochefert, Manfred; Couturier, Jean-François; Gaspers, Serge; Kratsch, Dieter
1
2016
List coloring in the absence of a linear forest. Zbl 1307.05068
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
17
2015
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1330.05118
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
15
2015
Exact algorithms for Kayles. Zbl 1305.05143
Bodlaender, Hans L.; Kratsch, Dieter; Timmer, Sjoerd T.
3
2015
End-vertices of graph search algorithms. Zbl 1459.68160
Kratsch, Dieter; Liedloff, Mathieu; Meister, Daniel
2
2015
Algorithms solving the matching cut problem. Zbl 1459.68159
Kratsch, Dieter; Le, Van Bang
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
22
2014
Subset feedback vertex sets in chordal graphs. Zbl 1298.05302
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
16
2014
Finding clubs in graph classes. Zbl 1298.05092
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash
11
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
2
2014
Exact algorithms to clique-colour graphs. Zbl 1432.05106
Cochefert, Manfred; Kratsch, Dieter
2
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
22
2013
Sparse square roots. Zbl 1331.05204
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
7
2013
Computing optimal Steiner trees in polynomial space. Zbl 1269.05049
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter; Lokshtanov, Daniel; Saurabh, Saket
6
2013
Fully decomposable split graphs. Zbl 1257.05125
Broersma, Hajo; Kratsch, Dieter; Woeginger, Gerhard J.
6
2013
Detecting induced minors in AT-free graphs. Zbl 1296.05183
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
4
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
3
2013
Exact algorithms for weak Roman domination. Zbl 1408.68112
Chapelle, Mathieu; Cochefert, Manfred; Couturier, Jean-François; Kratsch, Dieter; Liedloff, Mathieu; Perez, Anthony
3
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
2
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
2
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.
19
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.
16
2012
On independent sets and bicliques in graphs. Zbl 1239.05101
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
14
2012
Colouring AT-free graphs. Zbl 1365.68287
Kratsch, Dieter; Müller, Haiko
4
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
Bicolored independent sets and bicliques. Zbl 1243.68185
Couturier, Jean-François; 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
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
16
2011
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
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
10
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
191
2010
Parameterized algorithm for eternal vertex cover. Zbl 1234.68150
Fomin, Fedor V.; Gaspers, Serge; Golovach, Petr A.; Kratsch, Dieter; Saurabh, Saket
12
2010
Iterative compression and exact algorithms. Zbl 1186.68187
Fomin, Fedor V.; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket
12
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
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
Colorings with few colors: counting, enumeration and combinatorial bounds. Zbl 1309.05172
Golovach, Petr A.; Kratsch, Dieter; Couturier, Jean-Francois
2
2010
A measure & conquer approach for the analysis of exact algorithms. Zbl 1325.68311
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
82
2009
Convex recoloring revisited: complexity and exact algorithms. Zbl 1248.05201
Kanj, Iyad A.; Kratsch, Dieter
13
2009
Bandwidth of bipartite permutation graphs in polynomial time. Zbl 1209.05242
Heggernes, Pinar; Kratsch, Dieter; Meister, Daniel
10
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
9
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
38
2008
Exact algorithms for treewidth and minimum fill-in. Zbl 1163.05320
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve
34
2008
On independent sets and bicliques in graphs. Zbl 1202.05096
Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu
15
2008
Feedback vertex set on AT-free graphs. Zbl 1152.68044
Kratsch, Dieter; Müller, Haiko; Todinca, Ioan
12
2008
Faster Steiner tree computation in polynomial-space. Zbl 1158.68429
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
10
2008
Bandwidth of bipartite permutation graphs in polynomial time. Zbl 1136.05323
Heggernes, Pinar; Kratsch, Dieter; Meister, Daniel
3
2008
Iterative compression and exact algorithms. Zbl 1173.68537
Fomin, Fedor V.; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket
3
2008
A new characterization of HH-free graphs. Zbl 1226.05238
Kratsch, Dieter; Spinrad, Jeremy P.; Sritharan, R.
2
2008
Linear-time certifying recognition algorithms and forbidden induced subgraphs. Zbl 1169.68653
Heggernes, Pinar; Kratsch, Dieter
55
2007
Exact algorithms for graph homomorphisms. Zbl 1119.68133
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter
13
2007
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1147.05310
Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
9
2007
An exact algorithm for the minimum dominating clique problem. Zbl 1125.68135
Kratsch, Dieter; Liedloff, Mathieu
7
2007
Graph-theoretic concepts in computer science. 33rd international workshop, WG 2007, Dornburg, Germany, June 21–23, 2007. Revised papers. Zbl 1138.68002
1
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.
36
2006
Measure and conquer: a simple \(O(2^{0.288n})\) independent set algorithm. Zbl 1192.68960
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
34
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.
17
2006
...and 88 more Documents
all top 5

Cited by 1,855 Authors

92 Kratsch, Dieter
57 Paulusma, Daniël
46 Golovach, Petr A.
44 Heggernes, Pinar
41 Fomin, Fedor V.
37 Liedloff, Mathieu
33 Saurabh, Saket
30 Fernau, Henning
27 Xiao, Mingyu
26 Bodlaender, Hans L.
23 Kloks, Ton
23 Papadopoulos, Charis
21 Lokshtanov, Daniel
21 Lozin, Vadim Vladislavovich
20 Dragan, Feodor F.
20 Gaspers, Serge
20 Villanger, Yngve
19 Chang, Maw-Shang
19 Komusiewicz, Christian
19 Müller, Haiko
19 Raman, Venkatesh
18 Todinca, Ioan
17 Dabrowski, Konrad Kazimierz
17 Paschos, Vangelis Th.
16 Lê Văn Băng
16 Otachi, Yota
15 Ekim, Tınaz
15 Meister, Daniel
14 Brandstädt, Andreas
14 Niedermeier, Rolf
14 Pandey, Arti
14 Rzążewski, Paweł
13 Della Croce, Federico
13 Habib, Michel
13 Stewart, Lorna K.
13 Szwarcfiter, Jayme Luiz
13 Uno, Takeaki
12 Broersma, Hajo J.
12 Panda, Bhawani Sankar
12 Rossmanith, Peter
11 Corneil, Derek Gordon
11 Johnson, Matthew
11 Mosca, Raffaele
11 Nagamochi, Hiroshi
11 Pilipczuk, Michał
11 Suzuki, Akira
11 Thilikos, Dimitrios M.
10 Couturier, Jean-Francois
10 Cygan, Marek
10 Kanté, Mamadou Moustapha
10 Köhler, Ekkehard
10 Lingas, Andrzej
10 Milanič, Martin
10 Ono, Hirotaka
10 Peng, Sheng-Lung
10 Pilipczuk, Marcin L.
10 Sadagopan, Narasimhan
9 Chen, Li-Hsuan
9 Damaschke, Peter
9 de Figueiredo, Celina M. Herrera
9 Gimbel, John G.
9 Ito, Takehiro
9 Nešetřil, Jaroslav
9 Sampaio, Rudini Menezes
9 Subramani, Krishnan
9 T’kindt, Vincent
9 Uehara, Ryuhei
9 van ’t Hof, Pim
9 Zhou, Xiao
8 Berry, Anne
8 Binkele-Raible, Daniel
8 Brettell, Nick
8 Chaplick, Steven
8 Escoffier, Bruno
8 Junosza-Szaniawski, Konstanty
8 Kaski, Petteri
8 Kobayashi, Yasuaki
8 Kratochvíl, Jan
8 Misra, Neeldhara
8 Monnot, Jérôme
8 Munaro, Andrea
8 Narayan, Darren A.
8 Nikolopoulos, Stavros D.
8 van Rooij, Johan M. M.
7 Bazgan, Cristina
7 Casel, Katrin
7 Chandran, L. Sunil
7 Ducoffe, Guillaume
7 Grandoni, Fabrizio
7 Hung, Ling-Ju
7 Hung, Ruowei
7 Kowalik, Łukasz
7 Kowaluk, Mirosław
7 Mertzios, George B.
7 Mihai, Rodica
7 Nisse, Nicolas
7 Novotná, Jana
7 Ossona de Mendez, Patrice
7 Paesani, Giacomo
7 Philip, Geevarghese
...and 1,755 more Authors
all top 5

Cited in 132 Serials

252 Discrete Applied Mathematics
192 Theoretical Computer Science
120 Algorithmica
77 Information Processing Letters
75 Discrete Mathematics
36 Journal of Combinatorial Optimization
29 Theory of Computing Systems
28 SIAM Journal on Discrete Mathematics
25 Journal of Computer and System Sciences
22 Journal of Discrete Algorithms
18 Journal of Graph Theory
16 Graphs and Combinatorics
12 Networks
12 European Journal of Combinatorics
12 Discrete Mathematics, Algorithms and Applications
11 Information and Computation
11 European Journal of Operational Research
11 Discussiones Mathematicae. Graph Theory
9 Information Sciences
9 Order
9 International Journal of Foundations of Computer Science
9 The Electronic Journal of Combinatorics
9 Discrete Optimization
8 Computers & Operations Research
8 Journal of Graph Algorithms and Applications
8 Algorithms
7 SIAM Journal on Computing
7 Annals of Operations Research
7 International Journal of Computer Mathematics
7 Optimization Letters
6 Artificial Intelligence
6 Journal of Combinatorial Theory. Series B
6 Mathematical Programming. Series A. Series B
4 Applied Mathematics and Computation
4 International Transactions in Operational Research
4 INFORMS Journal on Computing
4 RAIRO. Operations Research
4 AKCE International Journal of Graphs and Combinatorics
4 Acta Universitatis Sapientiae. Informatica
3 Acta Informatica
3 Journal of Automated Reasoning
3 Computational Complexity
3 Annals of Mathematics and Artificial Intelligence
3 Journal of Scheduling
3 Annals of Combinatorics
3 Discrete Mathematics and Theoretical Computer Science. DMTCS
3 ACM Transactions on Algorithms
3 Computer Science Review
3 Prikladnaya Diskretnaya Matematika
2 BIT
2 Computing
2 International Journal of Game Theory
2 Journal of Combinatorial Theory. Series A
2 Advances in Applied Mathematics
2 Discrete & Computational Geometry
2 International Journal of Approximate Reasoning
2 Computational Geometry
2 Linear Algebra and its Applications
2 The Journal of Analysis
2 Journal of the ACM
2 Journal of Discrete Mathematical Sciences & Cryptography
2 Quantum Information Processing
2 4OR
2 ACM Journal of Experimental Algorithmics
2 Logical Methods in Computer Science
1 Bulletin of the Australian Mathematical Society
1 Communications in Mathematical Physics
1 Journal of Mathematical Biology
1 Rocky Mountain Journal of Mathematics
1 Automatica
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 Mathematics and Computers in Simulation
1 Operations Research
1 Pacific Journal of Mathematics
1 Transactions of the American Mathematical Society
1 Bulletin of the Korean Mathematical Society
1 Operations Research Letters
1 Combinatorica
1 Optimization
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 The Australasian Journal of Combinatorics
1 Cybernetics and Systems Analysis
1 Computational Optimization and Applications
1 Journal of Computer and Systems Sciences International
1 SIAM Journal on Scientific Computing
1 Journal of Mathematical Sciences (New York)
1 Computational and Applied Mathematics
1 Fractals
1 The Journal of Artificial Intelligence Research (JAIR)
1 Journal of Heuristics
...and 32 more Serials

Citations by Year