| 2008 |
|---|
| 109 | EE | Fedor V. Fomin,
Fabrizio Grandoni,
Dieter Kratsch:
Faster Steiner Tree Computation in Polynomial-Space.
ESA 2008: 430-441 |
| 108 | EE | Pinar Heggernes,
Dieter Kratsch,
Daniel Meister:
Bandwidth of Bipartite Permutation Graphs in Polynomial Time.
LATIN 2008: 216-227 |
| 107 | EE | Fedor V. Fomin,
Serge Gaspers,
Dieter Kratsch,
Mathieu Liedloff,
Saket Saurabh:
Iterative Compression and Exact Algorithms.
MFCS 2008: 335-346 |
| 106 | EE | Serge Gaspers,
Dieter Kratsch,
Mathieu Liedloff:
On Independent Sets and Bicliques in Graphs.
WG 2008: 171-182 |
| 105 | EE | Dieter Kratsch:
Exact Algorithms for Dominating Set.
Encyclopedia of Algorithms 2008 |
| 104 | EE | Fedor V. Fomin,
Fabrizio Grandoni,
Dieter Kratsch:
Solving Connected Dominating Set Faster than 2 n .
Algorithmica 52(2): 153-166 (2008) |
| 103 | EE | Dieter Kratsch,
Haiko Müller,
Ioan Todinca:
Feedback vertex set on AT-free graphs.
Discrete Applied Mathematics 156(10): 1936-1947 (2008) |
| 102 | EE | Dieter Kratsch,
Jeremy Spinrad,
R. Sritharan:
A new characterization of HH-free graphs.
Discrete Mathematics 308(20): 4833-4835 (2008) |
| 101 | EE | Fedor V. Fomin,
Dieter Kratsch,
Ioan Todinca,
Yngve Villanger:
Exact Algorithms for Treewidth and Minimum Fill-In.
SIAM J. Comput. 38(3): 1058-1079 (2008) |
| 2007 |
|---|
| 100 | | Andreas Brandstädt,
Klaus Jansen,
Dieter Kratsch,
Jeremy Spinrad:
Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes, 20.05. - 25.05.2007
Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2007 |
| 99 | | Andreas Brandstädt,
Dieter Kratsch,
Haiko Müller:
Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers
Springer 2007 |
| 98 | EE | Andreas Brandstädt,
Klaus Jansen,
Dieter Kratsch,
Jeremy Spinrad:
07211 Abstracts Collection - Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes.
Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes 2007 |
| 97 | EE | Jan Kratochvíl,
Dieter Kratsch,
Mathieu Liedloff:
Exact Algorithms for L (2, 1)-Labeling of Graphs.
MFCS 2007: 513-524 |
| 96 | EE | Fedor V. Fomin,
Petr A. Golovach,
Jan Kratochvíl,
Dieter Kratsch,
Mathieu Liedloff:
Branch and Recharge: Exact Algorithms for Generalized Domination.
WADS 2007: 507-518 |
| 95 | EE | Dieter Kratsch,
Mathieu Liedloff:
An exact algorithm for the minimum dominating clique problem.
Theor. Comput. Sci. 385(1-3): 226-240 (2007) |
| 94 | EE | Fedor V. Fomin,
Pinar Heggernes,
Dieter Kratsch:
Exact Algorithms for Graph Homomorphisms.
Theory Comput. Syst. 41(2): 381-393 (2007) |
| 2006 |
|---|
| 93 | EE | Hans L. Bodlaender,
Fedor V. Fomin,
Arie M. C. A. Koster,
Dieter Kratsch,
Dimitrios M. Thilikos:
On Exact Algorithms for Treewidth.
ESA 2006: 672-683 |
| 92 | EE | Fedor V. Fomin,
Fabrizio Grandoni,
Dieter Kratsch:
Solving Connected Dominating Set Faster Than 2n.
FSTTCS 2006: 152-163 |
| 91 | EE | Dieter Kratsch,
Mathieu Liedloff:
An Exact Algorithm for the Minimum Dominating Clique Problem.
IWPEC 2006: 130-141 |
| 90 | EE | Johanne Cohen,
Fedor V. Fomin,
Pinar Heggernes,
Dieter Kratsch,
Gregory Kucherov:
Optimal Linear Arrangement of Interval Graphs.
MFCS 2006: 267-279 |
| 89 | EE | Fedor V. Fomin,
Fabrizio Grandoni,
Dieter Kratsch:
Measure and conquer: a simple O(20.288n) independent set algorithm.
SODA 2006: 18-25 |
| 88 | EE | Serge Gaspers,
Dieter Kratsch,
Mathieu Liedloff:
Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes.
SWAT 2006: 148-159 |
| 87 | EE | Ton Kloks,
Dieter Kratsch,
Chuan-Min Lee,
Jiping Liu:
Improved bottleneck domination algorithms.
Discrete Applied Mathematics 154(11): 1578-1592 (2006) |
| 86 | EE | Dieter Kratsch,
Jeremy Spinrad:
Minimal fill in O(n2.69) time.
Discrete Mathematics 306(3): 366-371 (2006) |
| 85 | EE | Dieter Kratsch,
Jeremy Spinrad:
Between O(nm) and O(nalpha).
SIAM J. Comput. 36(2): 310-325 (2006) |
| 84 | EE | Dieter Kratsch,
Ross M. McConnell,
Kurt Mehlhorn,
Jeremy Spinrad:
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs.
SIAM J. Comput. 36(2): 326-353 (2006) |
| 2005 |
|---|
| 83 | | Dieter Kratsch:
Graph-Theoretic Concepts in Computer Science, 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers
Springer 2005 |
| 82 | EE | Maw-Shang Chang,
Ton Kloks,
Dieter Kratsch,
Jiping Liu,
Sheng-Lung Peng:
On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs.
COCOON 2005: 808-817 |
| 81 | EE | Fedor V. Fomin,
Pinar Heggernes,
Dieter Kratsch:
Exact Algorithms for Graph Homomorphisms.
FCT 2005: 161-171 |
| 80 | EE | Fedor V. Fomin,
Fabrizio Grandoni,
Dieter Kratsch:
Measure and Conquer: Domination - A Case Study.
ICALP 2005: 191-203 |
| 79 | | Fedor V. Fomin,
Fabrizio Grandoni,
Dieter Kratsch:
Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms.
Bulletin of the EATCS 87: 47-77 (2005) |
| 78 | EE | Andreas Brandstädt,
Dieter Kratsch:
On the structure of (P5, gem)-free graphs.
Discrete Applied Mathematics 145(2): 155-166 (2005) |
| 77 | EE | Hans L. Bodlaender,
Andreas Brandstädt,
Dieter Kratsch,
Michaël Rao,
Jeremy Spinrad:
On algorithms for (P5, gem)-free graphs.
Theor. Comput. Sci. 349(1): 2-21 (2005) |
| 2004 |
|---|
| 76 | EE | Fedor V. Fomin,
Dieter Kratsch,
Ioan Todinca:
Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In.
ICALP 2004: 568-580 |
| 75 | EE | Fedor V. Fomin,
Dieter Kratsch,
Gerhard J. Woeginger:
Exact (Exponential) Algorithms for the Dominating Set Problem.
WG 2004: 245-256 |
| 74 | EE | Fedor V. Fomin,
Dieter Kratsch,
Haiko Müller:
Algorithms for graphs with small octopus.
Discrete Applied Mathematics 134(1-3): 105-128 (2004) |
| 73 | EE | Vincent Bouchitté,
Dieter Kratsch,
Haiko Müller,
Ioan Todinca:
On treewidth approximations.
Discrete Applied Mathematics 136(2-3): 183-196 (2004) |
| 2003 |
|---|
| 72 | EE | Hans L. Bodlaender,
Andreas Brandstädt,
Dieter Kratsch,
Michaël Rao,
Jeremy Spinrad:
Linear Time Algorithms for Some NP-Complete Problems on (P5, Gem)-Free Graphs.
FCT 2003: 61-72 |
| 71 | EE | Dieter Kratsch,
Ross M. McConnell,
Kurt Mehlhorn,
Jeremy Spinrad:
Certifying algorithms for recognizing interval graphs and permutation graphs.
SODA 2003: 158-167 |
| 70 | EE | Dieter Kratsch,
Jeremy Spinrad:
Between O(nm) and O(n alpha).
SODA 2003: 709-716 |
| 69 | EE | Dieter Kratsch,
Haiko Müller,
Ioan Todinca:
Feedback Vertex Set and Longest Induced Path on AT-Free Graphs.
WG 2003: 309-321 |
| 68 | EE | Fedor V. Fomin,
Dieter Kratsch,
Haiko Müller:
On the Domination Search Number.
Discrete Applied Mathematics 127(3): 565-580 (2003) |
| 2002 |
|---|
| 67 | EE | Hajo Broersma,
Ton Kloks,
Dieter Kratsch,
Haiko Müller:
A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems.
Algorithmica 32(4): 594-610 (2002) |
| 66 | | Harald Hempel,
Dieter Kratsch:
On claw-free asteroidal triple-free graphs.
Discrete Applied Mathematics 121(1-3): 155-180 (2002) |
| 65 | EE | Fedor V. Fomin,
Dieter Kratsch,
Jean-Christophe Novelli:
Approximating minimum cocolorings.
Inf. Process. Lett. 84(5): 285-290 (2002) |
| 64 | EE | Hans L. Bodlaender,
Dieter Kratsch:
Kayles and Nimbers.
J. Algorithms 43(1): 106-119 (2002) |
| 63 | EE | Jitender S. Deogun,
Dieter Kratsch:
Dominating Pair Graphs.
SIAM J. Discrete Math. 15(3): 353-366 (2002) |
| 62 | EE | Dieter Kratsch,
Lorna Stewart:
Approximating Bandwidth by Mixing Layouts of Interval Graphs.
SIAM J. Discrete Math. 15(4): 435-449 (2002) |
| 2001 |
|---|
| 61 | EE | Fedor V. Fomin,
Dieter Kratsch,
Jean-Christophe Novelli:
Approximating Minimum Cocolourings.
FCT 2001: 118-125 |
| 60 | EE | Luitpold Babel,
Ton Kloks,
Jan Kratochvíl,
Dieter Kratsch,
Haiko Müller,
Stephan Olariu:
Efficient algorithms for graphs with few P4's.
Discrete Mathematics 235(1-3): 29-51 (2001) |
| 59 | EE | Vincent Bouchitté,
Dieter Kratsch,
Haiko Müller,
Ioan Todinca:
On treewidth approximations.
Electronic Notes in Discrete Mathematics 8: 98-101 (2001) |
| 58 | EE | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
On the Structure of Graphs with Bounded Asteroidal Number.
Graphs and Combinatorics 17(2): 295-306 (2001) |
| 2000 |
|---|
| 57 | EE | Fedor V. Fomin,
Dieter Kratsch,
Haiko Müller:
On the Domination Search Number.
WG 2000: 161-171 |
| 56 | EE | Ton Kloks,
Dieter Kratsch,
Yvan Le Borgne,
Haiko Müller:
Bandwidth of Split and Circular Permutation Graphs.
WG 2000: 243-254 |
| 55 | EE | Dieter Kratsch:
Domination and Total Domination on Asteroidal Triple-free Graphs.
Discrete Applied Mathematics 99(1-3): 111-123 (2000) |
| 54 | EE | Douglas Bauer,
Gyula Y. Katona,
Dieter Kratsch,
Henk Jan Veldman:
Chordality and 2-factors in Tough Graphs.
Discrete Applied Mathematics 99(1-3): 323-329 (2000) |
| 53 | EE | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Finding and counting small induced subgraphs efficiently.
Inf. Process. Lett. 74(3-4): 115-121 (2000) |
| 52 | EE | Hajo Broersma,
Otto R. Koppius,
Hilde Tuinstra,
Andreas Huck,
Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Degree-preserving trees.
Networks 35(1): 26-39 (2000) |
| 1999 |
|---|
| 51 | EE | Dieter Kratsch,
Lorna Stewart:
Approximating Bandwidth by Mixing Layouts of Interval Graphs.
STACS 1999: 248-258 |
| 50 | EE | Harald Hempel,
Dieter Kratsch:
On Claw-Free Asteroidal Triple-Free Graphs.
WG 1999: 377-390 |
| 49 | EE | Jitender S. Deogun,
Ton Kloks,
Dieter Kratsch,
Haiko Müller:
On the Vertex Ranking Problem for Trapezoid, Circular-arc and Other Graphs.
Discrete Applied Mathematics 98(1-2): 39-63 (1999) |
| 48 | EE | Dieter Kratsch,
Lorna Stewart:
Approximating Bandwidth by Mixing Layouts of Interval Graphs.
Electronic Notes in Discrete Mathematics 3: 106-109 (1999) |
| 47 | EE | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
On the structure of graphs with bounded asteroidal number.
Electronic Notes in Discrete Mathematics 3: 94 (1999) |
| 46 | | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Approximating the Bandwidth for Asteroidal Triple-Free Graphs.
J. Algorithms 32(1): 41-57 (1999) |
| 45 | EE | Hajo Broersma,
Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Independent Sets in Asteroidal Triple-Free Graphs.
SIAM J. Discrete Math. 12(2): 276-287 (1999) |
| 1998 |
|---|
| 44 | EE | Hajo Broersma,
Andreas Huck,
Ton Kloks,
Otto R. Koppius,
Dieter Kratsch,
Haiko Müller,
Hilde Tuinstra:
Degree-Preserving Forests.
MFCS 1998: 713-721 |
| 43 | | Hajo Broersma,
Ton Kloks,
Dieter Kratsch,
Haiko Müller:
A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking.
WG 1998: 88-99 |
| 42 | EE | Dieter Kratsch,
Jean-Xavier Rampon:
Tree-visibility orders.
Discrete Mathematics 190(1-3): 163-175 (1998) |
| 41 | EE | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Bandwidth of Chain Graphs.
Inf. Process. Lett. 68(6): 313-315 (1998) |
| 40 | | Ton Kloks,
Dieter Kratsch,
C. K. Wong:
Minimum Fill-in on Circle and Circular-Arc Graphs.
J. Algorithms 28(2): 272-289 (1998) |
| 39 | EE | Hans L. Bodlaender,
Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Treewidth and Minimum Fill-in on d-Trapezoid Graphs.
J. Graph Algorithms Appl. 2(2): (1998) |
| 38 | | Ton Kloks,
Dieter Kratsch:
Listing All Minimal Separators of a Graph.
SIAM J. Comput. 27(3): 605-613 (1998) |
| 37 | EE | Hans L. Bodlaender,
Jitender S. Deogun,
Klaus Jansen,
Ton Kloks,
Dieter Kratsch,
Haiko Müller,
Zsolt Tuza:
Rankings of Graphs.
SIAM J. Discrete Math. 11(1): 168-181 (1998) |
| 1997 |
|---|
| 36 | | Hajo Broersma,
Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Independent Sets in Asteroidal Triple-Free Graphs.
ICALP 1997: 760-770 |
| 35 | | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Asteroidal Sets in Graphs.
WG 1997: 229-241 |
| 34 | EE | Dieter Kratsch,
Ton Kloks,
Haiko Müller:
Measuring the Vulnerability for Classes of Intersection Graphs.
Discrete Applied Mathematics 77(3): 259-270 (1997) |
| 33 | EE | Jitender S. Deogun,
Dieter Kratsch,
George Steiner:
1-Tough cocomparability graphs are hamiltonian.
Discrete Mathematics 170(1-3): 99-106 (1997) |
| 32 | EE | Jitender S. Deogun,
Dieter Kratsch,
George Steiner:
An Approximation Algorithm for Clustering Graphs with Dominating Diametral Path.
Inf. Process. Lett. 61(3): 121-127 (1997) |
| 31 | EE | Dieter Kratsch,
Lorna Stewart:
Total Domination and Transformation.
Inf. Process. Lett. 63(3): 167-170 (1997) |
| 30 | EE | Ton Kloks,
Dieter Kratsch,
Jeremy Spinrad:
On Treewidth and Minimum Fill-In of Asteroidal Triple-Free Graphs.
Theor. Comput. Sci. 175(2): 309-335 (1997) |
| 1996 |
|---|
| 29 | | Ton Kloks,
Dieter Kratsch,
C. K. Wong:
Minimum Fill-In on Circle and Circular-Arc Graphs.
ICALP 1996: 256-267 |
| 28 | EE | Dieter Kratsch,
Jenö Lehel,
Haiko Müller:
Toughness, hamiltonicity and split graphs.
Discrete Mathematics 150(1-3): 231-245 (1996) |
| 27 | EE | Dieter Kratsch,
Jean-Xavier Rampon:
Width two posets are reconstructible.
Discrete Mathematics 162(1-3): 305-310 (1996) |
| 1995 |
|---|
| 26 | | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Approximating the Bandwidth for Asteroidal Triple-Free Graphs.
ESA 1995: 434-447 |
| 25 | | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Finding and Counting Small Induced Subgraphs Efficiently.
WG 1995: 14-23 |
| 24 | | Jitender S. Deogun,
Dieter Kratsch:
Diametral Path Graphs.
WG 1995: 344-357 |
| 23 | EE | Ton Kloks,
Dieter Kratsch:
Computing a Perfect Edge Without Vertex Elimination Ordering of a Chordal Bipartite Graph.
Inf. Process. Lett. 55(1): 11-16 (1995) |
| 22 | | Ton Kloks,
Dieter Kratsch:
Treewidth of Chordal Bipartite Graphs.
J. Algorithms 19(2): 266-281 (1995) |
| 21 | EE | Hans L. Bodlaender,
Ton Kloks,
Dieter Kratsch:
Treewidth and Pathwidth of Permutation Graphs.
SIAM J. Discrete Math. 8(4): 606-616 (1995) |
| 1994 |
|---|
| 20 | | Ton Kloks,
Hans L. Bodlaender,
Haiko Müller,
Dieter Kratsch:
Erratum: Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators.
ESA 1994: 508 |
| 19 | | Jitender S. Deogun,
Ton Kloks,
Dieter Kratsch,
Haiko Müller:
On Vertex Ranking for Permutations and Other Graphs.
STACS 1994: 747-758 |
| 18 | | Ton Kloks,
Dieter Kratsch:
Finding All Minimal Separators of a Graph.
STACS 1994: 759-768 |
| 17 | | Ton Kloks,
Dieter Kratsch,
Haiko Müller:
Dominoes.
WG 1994: 106-120 |
| 16 | | Hans L. Bodlaender,
Jitender S. Deogun,
Klaus Jansen,
Ton Kloks,
Dieter Kratsch,
Haiko Müller,
Zsolt Tuza:
Ranking of Graphs.
WG 1994: 292-304 |
| 15 | EE | John G. Gimbel,
Dieter Kratsch,
Lorna Stewart:
On Cocolourings and Cochromatic Numbers of Graphs.
Discrete Applied Mathematics 48(2): 111-127 (1994) |
| 14 | EE | Dieter Kratsch,
Peter Damaschke,
Anna Lubiw:
Dominating cliques in chordal graphs.
Discrete Mathematics 128(1-3): 269-275 (1994) |
| 13 | | Dieter Kratsch,
Lane A. Hemaspaandra:
On the Complexity of Graph Reconstruction.
Mathematical Systems Theory 27(3): 257-273 (1994) |
| 1993 |
|---|
| 12 | | Ton Kloks,
Hans L. Bodlaender,
Haiko Müller,
Dieter Kratsch:
Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators.
ESA 1993: 260-271 |
| 11 | | Hans L. Bodlaender,
Ton Kloks,
Dieter Kratsch:
Treewidth and Pathwidth of Permutation Graphs.
ICALP 1993: 114-125 |
| 10 | | Ton Kloks,
Dieter Kratsch:
Treewidth of Bipartite Graphs.
STACS 1993: 80-89 |
| 9 | | Dieter Kratsch,
Lorna Stewart:
Domination on Cocomparability Graphs.
SIAM J. Discrete Math. 6(3): 400-417 (1993) |
| 1992 |
|---|
| 8 | | Hans L. Bodlaender,
Dieter Kratsch:
The Complexity of Coloring Games on Perfect Graphs.
Theor. Comput. Sci. 106(2): 309-326 (1992) |
| 1991 |
|---|
| 7 | | Dieter Kratsch,
Lane A. Hemachandra:
On the Complexity of Graph Reconstruction.
FCT 1991: 318-328 |
| 1990 |
|---|
| 6 | EE | Dieter Kratsch:
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs.
Discrete Mathematics 86(1-3): 225-238 (1990) |
| 5 | | Peter Damaschke,
Haiko Müller,
Dieter Kratsch:
Domination in Convex and Chordal Bipartite Graphs.
Inf. Process. Lett. 36(5): 231-236 (1990) |
| 1987 |
|---|
| 4 | | Dieter Kratsch:
Finding the Minimum Bandwidth of an Interval Graphs
Inf. Comput. 74(2): 140-158 (1987) |
| 3 | | Andreas Brandstädt,
Dieter Kratsch:
On Domination Problems for Permutation and Other Graphs.
Theor. Comput. Sci. 54: 181-198 (1987) |
| 1986 |
|---|
| 2 | | Andreas Brandstädt,
Dieter Kratsch:
On Partitions of Permutations into Increasing and Decreasing Subsequences.
Elektronische Informationsverarbeitung und Kybernetik 22(5/6): 263-273 (1986) |
| 1985 |
|---|
| 1 | | Andreas Brandstädt,
Dieter Kratsch:
On the restriction of some NP-complete graph problems to permutation graphs.
FCT 1985: 53-62 |
