Dieter Kratsch

According to our database1, Dieter Kratsch authored at least 165 papers between 1985 and 2018.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of one.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Computing square roots of graphs with low maximum degree.
Discrete Applied Mathematics, 2018

Exact algorithms for weak Roman domination.
Discrete Applied Mathematics, 2018

Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms.
Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

2017
Exact exponential algorithms to find tropical connected sets of minimum size.
Theor. Comput. Sci., 2017

Minimal dominating sets in interval graphs and trees.
Discrete Applied Mathematics, 2017

Preface: Special graph classes and algorithms-in honor of Professor Andreas Brandstädt on the occasion of his 65th birthday.
Discrete Applied Mathematics, 2017

Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Enumerating Minimal Tropical Connected Sets.
Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs.
Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016
Exact Algorithms for Dominating Set.
Encyclopedia of Algorithms, 2016

Squares of Low Clique Number.
Electronic Notes in Discrete Mathematics, 2016

Enumerating minimal dominating sets in chordal bipartite graphs.
Discrete Applied Mathematics, 2016

Guest Editorial: Selected Papers from WG 2014.
Algorithmica, 2016

Parameterized Algorithms for Finding Square Roots.
Algorithmica, 2016

A Linear Kernel for Finding Square Roots of Almost Planar Graphs.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Faster Algorithms to Enumerate Hypergraph Transversals.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Finding Cactus Roots in Polynomial Time.
Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

2015
Exact algorithms for Kayles.
Theor. Comput. Sci., 2015

Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs.
Proceedings of the Combinatorial Algorithms - 26th International Workshop, 2015

Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

End-Vertices of Graph Search Algorithms.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

Algorithms Solving the Matching Cut Problem.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014
Subset feedback vertex sets in chordal graphs.
J. Discrete Algorithms, 2014

Finding clubs in graph classes.
Discrete Applied Mathematics, 2014

Exact Algorithms to Clique-Colour Graphs.
Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Finding Shortest Paths Between Graph Colourings.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

2013
Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds.
Theory Comput. Syst., 2013

Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization.
Inf. Comput., 2013

Computing Optimal Steiner Trees in Polynomial Space.
Algorithmica, 2013

Sparse Square Roots.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

The Jump Number Problem: Exact and Parameterized.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Exact Algorithms for Weak Roman Domination.
Proceedings of the Combinatorial Algorithms - 24th International Workshop, 2013

An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Cliques and Clubs.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2012
A Note on Exact Algorithms for Vertex Ordering Problems on Graphs.
Theory Comput. Syst., 2012

On the parameterized complexity of coloring graphs in the absence of a linear forest.
J. Discrete Algorithms, 2012

Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration.
Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012

An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

Detecting Induced Minors in AT-Free Graphs.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Colouring AT-Free Graphs.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Breaking the 2n-barrier for Irredundance: Two lines of attack.
J. Discrete Algorithms, 2011

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

List Coloring in the Absence of a Linear Forest.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

Exact Algorithms for Kayles.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

Enumerating Minimal Subset Feedback Vertex Sets.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Bicolored independent sets and bicliques.
Proceedings of the 10th Cologne-Twente Workshop on graphs and combinatorial optimization. Extended Abstracts, 2011

2010
Exact Exponential Algorithms
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-642-16533-7, 2010

Parameterized algorithm for eternal vertex cover.
Inf. Process. Lett., 2010

Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing.
Proceedings of the Algorithm Theory, 2010

10441 Abstracts Collection - Exact Complexity of NP-hard Problems.
Proceedings of the Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010, 2010

A Parameterized Route to Exact Puzzles: Breaking the 2n-Barrier for Irredundance.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009
Exponential time algorithms for the minimum dominating set problem on some graph classes.
ACM Trans. Algorithms, 2009

A measure & conquer approach for the analysis of exact algorithms.
J. ACM, 2009

Sort and Search: Exact algorithms for generalized domination.
Inf. Process. Lett., 2009

On a property of minimal triangulations.
Discrete Mathematics, 2009

An Exact Algorithm for the Maximum Leaf Spanning Tree Problem.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Fully Decomposable Split Graphs.
Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

Bandwidth on AT-Free Graphs.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Exact Exponential-Time Algorithms for Finding Bicliques in a Graph.
Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2009

Convex Recoloring Revisited: Complexity and Exact Algorithms.
Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008
Exact Algorithms for Dominating Set.
Proceedings of the Encyclopedia of Algorithms, 2008

Exact Algorithms for Treewidth and Minimum Fill-In.
SIAM J. Comput., 2008

A new characterization of HH-free graphs.
Discrete Mathematics, 2008

Feedback vertex set on AT-free graphs.
Discrete Applied Mathematics, 2008

Solving Connected Dominating Set Faster than 2 n .
Algorithmica, 2008

On Independent Sets and Bicliques in Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Iterative Compression and Exact Algorithms.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Bandwidth of Bipartite Permutation Graphs in Polynomial Time.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Faster Steiner Tree Computation in Polynomial-Space.
Proceedings of the Algorithms, 2008

08431 Open Problems - Moderately Exponential Time Algorithms.
Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

08431 Executive Summary - Moderately Exponential Time Algorithms.
Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

08431 Abstracts Collection - Moderately Exponential Time Algorithms.
Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

2007
Linear-time certifying recognition algorithms and forbidden induced subgraphs.
Nord. J. Comput., 2007

Branch and Recharge: Exact Algorithms for Generalized Domination.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Exact Algorithms for L (2, 1)-Labeling of Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

07211 Abstracts Collection - Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes.
Proceedings of the Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes, 20.05., 2007

2006
Between O(nm) and O(nalpha).
SIAM J. Comput., 2006

Minimal fill in O(n2.69) time.
Discrete Mathematics, 2006

Improved bottleneck domination algorithms.
Discrete Applied Mathematics, 2006

Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes.
Proceedings of the Algorithm Theory, 2006

Measure and conquer: a simple O(20.288n) independent set algorithm.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Optimal Linear Arrangement of Interval Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

An Exact Algorithm for the Minimum Dominating Clique Problem.
Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

Solving Connected Dominating Set Faster Than 2n.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

On Exact Algorithms for Treewidth.
Proceedings of the Algorithms, 2006

2005
On algorithms for (P5, gem)-free graphs.
Theor. Comput. Sci., 2005

Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms.
Bulletin of the EATCS, 2005

On the structure of (P5, gem)-free graphs.
Discrete Applied Mathematics, 2005

Measure and Conquer: Domination - A Case Study.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Exact Algorithms for Graph Homomorphisms.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004
Algorithms for graphs with small octopus.
Discrete Applied Mathematics, 2004

On treewidth approximations.
Discrete Applied Mathematics, 2004

Exact (Exponential) Algorithms for the Dominating Set Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
Feedback Vertex Set and Longest Induced Path on AT-Free Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

Between O(nm) and O(n alpha).
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Certifying algorithms for recognizing interval graphs and permutation graphs.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Linear Time Algorithms for Some NP-Complete Problems on (P5, Gem)-Free Graphs.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002
Dominating Pair Graphs.
SIAM J. Discrete Math., 2002

Kayles and Nimbers.
J. Algorithms, 2002

Approximating minimum cocolorings.
Inf. Process. Lett., 2002

A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems.
Algorithmica, 2002

2001
On the Structure of Graphs with Bounded Asteroidal Number.
Graphs and Combinatorics, 2001

On treewidth approximations.
Electronic Notes in Discrete Mathematics, 2001

Efficient algorithms for graphs with few P4's.
Discrete Mathematics, 2001

Approximating Minimum Cocolourings.
Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 2001

2000
Degree-preserving trees.
Networks, 2000

Domination and Total Domination on Asteroidal Triple-free Graphs.
Discrete Applied Mathematics, 2000

Chordality and 2-factors in Tough Graphs.
Discrete Applied Mathematics, 2000

Bandwidth of Split and Circular Permutation Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2000

On the Domination Search Number.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2000

1999
On the structure of graphs with bounded asteroidal number.
Electronic Notes in Discrete Mathematics, 1999

On the Vertex Ranking Problem for Trapezoid, Circular-arc and Other Graphs.
Discrete Applied Mathematics, 1999

On Claw-Free Asteroidal Triple-Free Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

Approximating Bandwidth by Mixing Layouts of Interval Graphs.
Proceedings of the STACS 99, 1999

1998
Rankings of Graphs.
SIAM J. Discrete Math., 1998

Listing All Minimal Separators of a Graph.
SIAM J. Comput., 1998

Treewidth and Minimum Fill-in on d-Trapezoid Graphs.
J. Graph Algorithms Appl., 1998

Bandwidth of Chain Graphs.
Inf. Process. Lett., 1998

Tree-visibility orders.
Discrete Mathematics, 1998

A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

Degree-Preserving Forests.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997
On Treewidth and Minimum Fill-In of Asteroidal Triple-Free Graphs.
Theor. Comput. Sci., 1997

Total Domination and Transformation.
Inf. Process. Lett., 1997

An Approximation Algorithm for Clustering Graphs with Dominating Diametral Path.
Inf. Process. Lett., 1997

1-Tough cocomparability graphs are hamiltonian.
Discrete Mathematics, 1997

Measuring the Vulnerability for Classes of Intersection Graphs.
Discrete Applied Mathematics, 1997

Asteroidal Sets in Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

Independent Sets in Asteroidal Triple-Free Graphs.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996
Minimal non-neighborhood-perfect graphs.
Journal of Graph Theory, 1996

Width two posets are reconstructible.
Discrete Mathematics, 1996

Toughness, hamiltonicity and split graphs.
Discrete Mathematics, 1996

Minimum Fill-In on Circle and Circular-Arc Graphs.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
Treewidth of Chordal Bipartite Graphs.
J. Algorithms, 1995

Computing a Perfect Edge Without Vertex Elimination Ordering of a Chordal Bipartite Graph.
Inf. Process. Lett., 1995

Finding and Counting Small Induced Subgraphs Efficiently.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995

Diametral Path Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995

Approximating the Bandwidth for Asteroidal Triple-Free Graphs.
Proceedings of the Algorithms, 1995

1994
Book reviews.
Math. Meth. of OR, 1994

Dominating cliques in chordal graphs.
Discrete Mathematics, 1994

On Cocolourings and Cochromatic Numbers of Graphs.
Discrete Applied Mathematics, 1994

Dominoes.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

Ranking of Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

Finding All Minimal Separators of a Graph.
Proceedings of the STACS 94, 1994

On Vertex Ranking for Permutations and Other Graphs.
Proceedings of the STACS 94, 1994

Erratum: Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators.
Proceedings of the Algorithms, 1994

1993
Domination on Cocomparability Graphs.
SIAM J. Discrete Math., 1993

Treewidth of Bipartite Graphs.
Proceedings of the STACS 93, 1993

Treewidth and Pathwidth of Permutation Graphs.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators.
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

1992
The Complexity of Coloring Games on Perfect Graphs.
Theor. Comput. Sci., 1992

1991
Some extremal results in cochromatic and dichromatic theory.
Journal of Graph Theory, 1991

On the Complexity of Graph Reconstruction.
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990
Domination in Convex and Chordal Bipartite Graphs.
Inf. Process. Lett., 1990

Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs.
Discrete Mathematics, 1990

1987
Finding the Minimum Bandwidth of an Interval Graphs
Inf. Comput., August, 1987

On Domination Problems for Permutation and Other Graphs.
Theor. Comput. Sci., 1987

1986
On Partitions of Permutations into Increasing and Decreasing Subsequences.
Elektronische Informationsverarbeitung und Kybernetik, 1986

1985
On the restriction of some NP-complete graph problems to permutation graphs.
Proceedings of the Fundamentals of Computation Theory, 1985


  Loading...