default search action
BibTeX records: Dieter Kratsch
@article{DBLP:journals/jcss/GolovachKKL22,
author = {Petr A. Golovach and
Christian Komusiewicz and
Dieter Kratsch and
Van Bang Le},
title = {Refined notions of parameterized enumeration kernels with applications
to matching cut enumeration},
journal = {J. Comput. Syst. Sci.},
volume = {123},
pages = {76--102},
year = {2022}
}
@inproceedings{DBLP:conf/stacs/GolovachKKL21,
author = {Petr A. Golovach and
Christian Komusiewicz and
Dieter Kratsch and
Van Bang Le},
title = {Refined Notions of Parameterized Enumeration Kernels with Applications
to Matching Cut Enumeration},
booktitle = {{STACS}},
series = {LIPIcs},
volume = {187},
pages = {37:1--37:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021}
}
@article{DBLP:journals/corr/abs-2101-03800,
author = {Petr A. Golovach and
Christian Komusiewicz and
Dieter Kratsch and
Van Bang Le},
title = {Refined Notions of Parameterized Enumeration Kernels with Applications
to Matching Cut Enumeration},
journal = {CoRR},
volume = {abs/2101.03800},
year = {2021}
}
@article{DBLP:journals/dam/GolovachHKS20,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Reza Saei},
title = {Enumeration of minimal connected dominating sets for chordal graphs},
journal = {Discret. Appl. Math.},
volume = {278},
pages = {3--11},
year = {2020}
}
@article{DBLP:journals/dam/KomusiewiczKL20,
author = {Christian Komusiewicz and
Dieter Kratsch and
Van Bang Le},
title = {Matching cut: Kernelization, single-exponential time FPT, and exact
exponential algorithms},
journal = {Discret. Appl. Math.},
volume = {283},
pages = {44--58},
year = {2020}
}
@article{DBLP:journals/algorithmica/KammerKL19,
author = {Frank Kammer and
Dieter Kratsch and
Moritz Laudahn},
title = {Space-Efficient Biconnected Components and Recognition of Outerplanar
Graphs},
journal = {Algorithmica},
volume = {81},
number = {3},
pages = {1180--1204},
year = {2019}
}
@article{DBLP:journals/algorithmica/GolovachHKLP19,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Paloma T. Lima and
Dani{\"{e}}l Paulusma},
title = {Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth
at Most 2},
journal = {Algorithmica},
volume = {81},
number = {7},
pages = {2795--2828},
year = {2019}
}
@article{DBLP:journals/dam/GolovachKLS19,
author = {Petr A. Golovach and
Dieter Kratsch and
Mathieu Liedloff and
Mohamed Yosri Sayadi},
title = {Enumeration and maximum number of maximal irredundant sets for chordal
graphs},
journal = {Discret. Appl. Math.},
volume = {265},
pages = {69--85},
year = {2019}
}
@article{DBLP:journals/tcs/GolovachKS19,
author = {Petr A. Golovach and
Dieter Kratsch and
Mohamed Yosri Sayadi},
title = {Enumeration of maximal irredundant sets for claw-free graphs},
journal = {Theor. Comput. Sci.},
volume = {754},
pages = {3--15},
year = {2019}
}
@article{DBLP:journals/tcs/GolovachKLS19,
author = {Petr A. Golovach and
Dieter Kratsch and
Mathieu Liedloff and
Mohamed Yosri Sayadi},
title = {Enumeration and maximum number of minimal dominating sets for chordal
graphs},
journal = {Theor. Comput. Sci.},
volume = {783},
pages = {41--52},
year = {2019}
}
@article{DBLP:journals/algorithmica/GolovachHKKSV18,
author = {Petr A. Golovach and
Pinar Heggernes and
Mamadou Moustapha Kant{\'{e}} and
Dieter Kratsch and
Sigve Hortemo S{\ae}ther and
Yngve Villanger},
title = {Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear
MIM-Width},
journal = {Algorithmica},
volume = {80},
number = {2},
pages = {714--741},
year = {2018}
}
@article{DBLP:journals/dam/ChapelleCCKLLP18,
author = {Mathieu Chapelle and
Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Dieter Kratsch and
Romain Letourneur and
Mathieu Liedloff and
Anthony Perez},
title = {Exact algorithms for weak Roman domination},
journal = {Discret. Appl. Math.},
volume = {248},
pages = {79--92},
year = {2018}
}
@article{DBLP:journals/dam/CochefertCGKPS18,
author = {Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma and
Anthony Stewart},
title = {Computing square roots of graphs with low maximum degree},
journal = {Discret. Appl. Math.},
volume = {248},
pages = {93--101},
year = {2018}
}
@article{DBLP:journals/ejc/GolovachHK18,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch},
title = {Enumeration and maximum number of minimal connected vertex covers
in graphs},
journal = {Eur. J. Comb.},
volume = {68},
pages = {132--147},
year = {2018}
}
@article{DBLP:journals/mst/GolovachKPS18,
author = {Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma and
Anthony Stewart},
title = {Finding Cactus Roots in Polynomial Time},
journal = {Theory Comput. Syst.},
volume = {62},
number = {6},
pages = {1409--1426},
year = {2018}
}
@inproceedings{DBLP:conf/iwpec/KomusiewiczKL18,
author = {Christian Komusiewicz and
Dieter Kratsch and
Van Bang Le},
title = {Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact
Exponential Algorithms},
booktitle = {{IPEC}},
series = {LIPIcs},
volume = {115},
pages = {19:1--19:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018}
}
@article{DBLP:journals/dam/DraganKL17,
author = {Feodor F. Dragan and
Dieter Kratsch and
Van Bang Le},
title = {Preface: Special graph classes and algorithms-in honor of Professor
Andreas Brandst{\"{a}}dt on the occasion of his 65th birthday},
journal = {Discret. Appl. Math.},
volume = {216},
pages = {1},
year = {2017}
}
@article{DBLP:journals/dam/GolovachHKKV17,
author = {Petr A. Golovach and
Pinar Heggernes and
Mamadou Moustapha Kant{\'{e}} and
Dieter Kratsch and
Yngve Villanger},
title = {Minimal dominating sets in interval graphs and trees},
journal = {Discret. Appl. Math.},
volume = {216},
pages = {162--170},
year = {2017}
}
@article{DBLP:journals/tcs/ChapelleCKLL17,
author = {Mathieu Chapelle and
Manfred Cochefert and
Dieter Kratsch and
Romain Letourneur and
Mathieu Liedloff},
title = {Exact exponential algorithms to find tropical connected sets of minimum
size},
journal = {Theor. Comput. Sci.},
volume = {676},
pages = {33--41},
year = {2017}
}
@article{DBLP:journals/tcs/GolovachKPS17,
author = {Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma and
Anthony Stewart},
title = {A linear kernel for finding square roots of almost planar graphs},
journal = {Theor. Comput. Sci.},
volume = {689},
pages = {36--47},
year = {2017}
}
@inproceedings{DBLP:conf/ciac/GolovachKS17,
author = {Petr A. Golovach and
Dieter Kratsch and
Mohamed Yosri Sayadi},
title = {Enumeration of Maximal Irredundant Sets for Claw-Free Graphs},
booktitle = {{CIAC}},
series = {Lecture Notes in Computer Science},
volume = {10236},
pages = {297--309},
year = {2017}
}
@inproceedings{DBLP:conf/sofsem/KratschLS17,
author = {Dieter Kratsch and
Mathieu Liedloff and
Mohamed Yosri Sayadi},
title = {Enumerating Minimal Tropical Connected Sets},
booktitle = {{SOFSEM}},
series = {Lecture Notes in Computer Science},
volume = {10139},
pages = {217--228},
publisher = {Springer},
year = {2017}
}
@inproceedings{DBLP:conf/wg/GolovachHKLP17,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Paloma T. Lima and
Dani{\"{e}}l Paulusma},
title = {Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth
at Most 2},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {10520},
pages = {275--288},
publisher = {Springer},
year = {2017}
}
@inproceedings{DBLP:conf/wg/GolovachKLS17,
author = {Petr A. Golovach and
Dieter Kratsch and
Mathieu Liedloff and
Mohamed Yosri Sayadi},
title = {Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal
Graphs},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {10520},
pages = {289--302},
publisher = {Springer},
year = {2017}
}
@article{DBLP:journals/corr/GolovachHKLP17,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Paloma T. Lima and
Dani{\"{e}}l Paulusma},
title = {Algorithms for outerplanar graph roots and graph roots of pathwidth
at most 2},
journal = {CoRR},
volume = {abs/1703.05102},
year = {2017}
}
@article{DBLP:journals/algorithmica/Cochefert0GKP16,
author = {Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma},
title = {Parameterized Algorithms for Finding Square Roots},
journal = {Algorithmica},
volume = {74},
number = {2},
pages = {602--629},
year = {2016}
}
@article{DBLP:journals/algorithmica/KratschT16,
author = {Dieter Kratsch and
Ioan Todinca},
title = {Guest Editorial: Selected Papers from {WG} 2014},
journal = {Algorithmica},
volume = {75},
number = {1},
pages = {186},
year = {2016}
}
@article{DBLP:journals/algorithmica/0001KKPP16,
author = {Matthew Johnson and
Dieter Kratsch and
Stefan Kratsch and
Viresh Patel and
Dani{\"{e}}l Paulusma},
title = {Finding Shortest Paths Between Graph Colourings},
journal = {Algorithmica},
volume = {75},
number = {2},
pages = {295--321},
year = {2016}
}
@article{DBLP:journals/dam/GolovachHKKV16,
author = {Petr A. Golovach and
Pinar Heggernes and
Mamadou Moustapha Kant{\'{e}} and
Dieter Kratsch and
Yngve Villanger},
title = {Enumerating minimal dominating sets in chordal bipartite graphs},
journal = {Discret. Appl. Math.},
volume = {199},
pages = {30--36},
year = {2016}
}
@article{DBLP:journals/endm/GolovachKPS16,
author = {Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma and
Anthony Stewart},
title = {Squares of Low Clique Number},
journal = {Electron. Notes Discret. Math.},
volume = {55},
pages = {195--198},
year = {2016}
}
@article{DBLP:journals/tcs/KratschL16,
author = {Dieter Kratsch and
Van Bang Le},
title = {Algorithms solving the Matching Cut problem},
journal = {Theor. Comput. Sci.},
volume = {609},
pages = {328--335},
year = {2016}
}
@article{DBLP:journals/tcs/GolovachHK16,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch},
title = {Enumerating minimal connected dominating sets in graphs of bounded
chordality},
journal = {Theor. Comput. Sci.},
volume = {630},
pages = {63--75},
year = {2016}
}
@inproceedings{DBLP:conf/iwoca/GolovachKPS16,
author = {Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma and
Anthony Stewart},
title = {Finding Cactus Roots in Polynomial Time},
booktitle = {{IWOCA}},
series = {Lecture Notes in Computer Science},
volume = {9843},
pages = {361--372},
publisher = {Springer},
year = {2016}
}
@inproceedings{DBLP:conf/latin/Cochefert0GK16,
author = {Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Serge Gaspers and
Dieter Kratsch},
title = {Faster Algorithms to Enumerate Hypergraph Transversals},
booktitle = {{LATIN}},
series = {Lecture Notes in Computer Science},
volume = {9644},
pages = {306--318},
publisher = {Springer},
year = {2016}
}
@inproceedings{DBLP:conf/mfcs/KammerKL16,
author = {Frank Kammer and
Dieter Kratsch and
Moritz Laudahn},
title = {Space-Efficient Biconnected Components and Recognition of Outerplanar
Graphs},
booktitle = {{MFCS}},
series = {LIPIcs},
volume = {58},
pages = {56:1--56:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016}
}
@inproceedings{DBLP:conf/swat/GolovachKPS16,
author = {Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma and
Anthony Stewart},
title = {A Linear Kernel for Finding Square Roots of Almost Planar Graphs},
booktitle = {{SWAT}},
series = {LIPIcs},
volume = {53},
pages = {4:1--4:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016}
}
@incollection{DBLP:reference/algo/Kratsch16,
author = {Dieter Kratsch},
title = {Exact Algorithms for Dominating Set},
booktitle = {Encyclopedia of Algorithms},
pages = {667--670},
year = {2016}
}
@article{DBLP:journals/corr/GolovachHK16,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch},
title = {Enumeration and Maximum Number of Minimal Connected Vertex Covers
in Graphs},
journal = {CoRR},
volume = {abs/1602.07504},
year = {2016}
}
@article{DBLP:journals/corr/KammerKL16,
author = {Frank Kammer and
Dieter Kratsch and
Moritz Laudahn},
title = {Space-Efficient Biconnected Components and Recognition of Outerplanar
Graphs},
journal = {CoRR},
volume = {abs/1606.04679},
year = {2016}
}
@article{DBLP:journals/corr/GolovachKPS16,
author = {Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma and
Anthony Stewart},
title = {A Linear Kernel for Finding Square Roots of Almost Planar Graphs},
journal = {CoRR},
volume = {abs/1608.06136},
year = {2016}
}
@article{DBLP:journals/corr/Cochefert0GKPS16,
author = {Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma and
Anthony Stewart},
title = {Squares of Low Maximum Degree},
journal = {CoRR},
volume = {abs/1608.06142},
year = {2016}
}
@article{DBLP:journals/algorithmica/0001GKP15,
author = {Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma},
title = {List Coloring in the Absence of a Linear Forest},
journal = {Algorithmica},
volume = {71},
number = {1},
pages = {21--35},
year = {2015}
}
@article{DBLP:journals/algorithmica/GolovachHKV15,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Yngve Villanger},
title = {An Incremental Polynomial Time Algorithm to Enumerate All Minimal
Edge Dominating Sets},
journal = {Algorithmica},
volume = {72},
number = {3},
pages = {836--859},
year = {2015}
}
@article{DBLP:journals/tcs/BodlaenderKT15,
author = {Hans L. Bodlaender and
Dieter Kratsch and
Sjoerd T. Timmer},
title = {Exact algorithms for Kayles},
journal = {Theor. Comput. Sci.},
volume = {562},
pages = {165--176},
year = {2015}
}
@inproceedings{DBLP:conf/ciac/KratschL15,
author = {Dieter Kratsch and
Van Bang Le},
title = {Algorithms Solving the Matching Cut Problem},
booktitle = {{CIAC}},
series = {Lecture Notes in Computer Science},
volume = {9079},
pages = {288--299},
publisher = {Springer},
year = {2015}
}
@inproceedings{DBLP:conf/ciac/KratschLM15,
author = {Dieter Kratsch and
Mathieu Liedloff and
Daniel Meister},
title = {End-Vertices of Graph Search Algorithms},
booktitle = {{CIAC}},
series = {Lecture Notes in Computer Science},
volume = {9079},
pages = {300--312},
publisher = {Springer},
year = {2015}
}
@inproceedings{DBLP:conf/isaac/GolovachHKKSV15,
author = {Petr A. Golovach and
Pinar Heggernes and
Mamadou Moustapha Kant{\'{e}} and
Dieter Kratsch and
Sigve Hortemo S{\ae}ther and
Yngve Villanger},
title = {Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear
MIM-Width},
booktitle = {{ISAAC}},
series = {Lecture Notes in Computer Science},
volume = {9472},
pages = {248--258},
publisher = {Springer},
year = {2015}
}
@inproceedings{DBLP:conf/iwoca/GolovachHK15,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch},
title = {Enumeration and Maximum Number of Minimal Connected Vertex Covers
in Graphs},
booktitle = {{IWOCA}},
series = {Lecture Notes in Computer Science},
volume = {9538},
pages = {235--247},
publisher = {Springer},
year = {2015}
}
@inproceedings{DBLP:conf/iwpec/GolovachHK15,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch},
title = {Enumerating Minimal Connected Dominating Sets in Graphs of Bounded
Chordality},
booktitle = {{IPEC}},
series = {LIPIcs},
volume = {43},
pages = {307--318},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015}
}
@article{DBLP:journals/corr/GolovachHKKSV15,
author = {Petr A. Golovach and
Pinar Heggernes and
Mamadou Moustapha Kant{\'{e}} and
Dieter Kratsch and
Sigve Hortemo S{\ae}ther and
Yngve Villanger},
title = {Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear
MIM-Width},
journal = {CoRR},
volume = {abs/1509.03753},
year = {2015}
}
@article{DBLP:journals/corr/Cochefert0GK15,
author = {Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Serge Gaspers and
Dieter Kratsch},
title = {Faster algorithms to enumerate hypergraph transversals},
journal = {CoRR},
volume = {abs/1510.05093},
year = {2015}
}
@article{DBLP:journals/algorithmica/FominHKPV14,
author = {Fedor V. Fomin and
Pinar Heggernes and
Dieter Kratsch and
Charis Papadopoulos and
Yngve Villanger},
title = {Enumerating Minimal Subset Feedback Vertex Sets},
journal = {Algorithmica},
volume = {69},
number = {1},
pages = {216--231},
year = {2014}
}
@article{DBLP:journals/dam/GolovachHKR14,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Arash Rafiey},
title = {Finding clubs in graph classes},
journal = {Discret. Appl. Math.},
volume = {174},
pages = {57--65},
year = {2014}
}
@article{DBLP:journals/jda/GolovachHKS14,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Reza Saei},
title = {Subset feedback vertex sets in chordal graphs},
journal = {J. Discrete Algorithms},
volume = {26},
pages = {7--15},
year = {2014}
}
@inproceedings{DBLP:conf/iwpec/ChapelleCKLL14,
author = {Mathieu Chapelle and
Manfred Cochefert and
Dieter Kratsch and
Romain Letourneur and
Mathieu Liedloff},
title = {Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum
Size},
booktitle = {{IPEC}},
series = {Lecture Notes in Computer Science},
volume = {8894},
pages = {147--158},
publisher = {Springer},
year = {2014}
}
@inproceedings{DBLP:conf/iwpec/0002KKPP14,
author = {Matthew Johnson and
Dieter Kratsch and
Stefan Kratsch and
Viresh Patel and
Dani{\"{e}}l Paulusma},
title = {Finding Shortest Paths Between Graph Colourings},
booktitle = {{IPEC}},
series = {Lecture Notes in Computer Science},
volume = {8894},
pages = {221--233},
publisher = {Springer},
year = {2014}
}
@inproceedings{DBLP:conf/sofsem/CochefertK14,
author = {Manfred Cochefert and
Dieter Kratsch},
title = {Exact Algorithms to Clique-Colour Graphs},
booktitle = {{SOFSEM}},
series = {Lecture Notes in Computer Science},
volume = {8327},
pages = {187--198},
publisher = {Springer},
year = {2014}
}
@proceedings{DBLP:conf/wg/2014,
editor = {Dieter Kratsch and
Ioan Todinca},
title = {Graph-Theoretic Concepts in Computer Science - 40th International
Workshop, {WG} 2014, Nouan-le-Fuzelier, France, June 25-27, 2014.
Revised Selected Papers},
series = {Lecture Notes in Computer Science},
volume = {8747},
publisher = {Springer},
year = {2014}
}
@article{DBLP:journals/corr/0002KKPP14,
author = {Matthew Johnson and
Dieter Kratsch and
Stefan Kratsch and
Viresh Patel and
Dani{\"{e}}l Paulusma},
title = {Colouring Reconfiguration Is Fixed-Parameter Tractable},
journal = {CoRR},
volume = {abs/1403.6347},
year = {2014}
}
@article{DBLP:journals/algorithmica/FominGKLS13,
author = {Fedor V. Fomin and
Fabrizio Grandoni and
Dieter Kratsch and
Daniel Lokshtanov and
Saket Saurabh},
title = {Computing Optimal Steiner Trees in Polynomial Space},
journal = {Algorithmica},
volume = {65},
number = {3},
pages = {584--604},
year = {2013}
}
@article{DBLP:journals/ejc/BroersmaKW13,
author = {Hajo Broersma and
Dieter Kratsch and
Gerhard J. Woeginger},
title = {Fully decomposable split graphs},
journal = {Eur. J. Comb.},
volume = {34},
number = {3},
pages = {567--575},
year = {2013}
}
@article{DBLP:journals/iandc/HeggernesKLRS13,
author = {Pinar Heggernes and
Dieter Kratsch and
Daniel Lokshtanov and
Venkatesh Raman and
Saket Saurabh},
title = {Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle
Stabbing via iterative localization},
journal = {Inf. Comput.},
volume = {231},
pages = {109--116},
year = {2013}
}
@article{DBLP:journals/mst/CouturierGKLP13,
author = {Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Mathieu Liedloff and
Artem V. Pyatkin},
title = {Colorings with few Colors: Counting, Enumeration and Combinatorial
Bounds},
journal = {Theory Comput. Syst.},
volume = {52},
number = {4},
pages = {645--667},
year = {2013}
}
@article{DBLP:journals/tcs/GolovachKP13,
author = {Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma},
title = {Detecting induced minors in AT-free graphs},
journal = {Theor. Comput. Sci.},
volume = {482},
pages = {20--32},
year = {2013}
}
@article{DBLP:journals/tcs/CouturierHHK13,
author = {Jean{-}Fran{\c{c}}ois Couturier and
Pinar Heggernes and
Pim van 't Hof and
Dieter Kratsch},
title = {Minimal dominating sets in graph classes: Combinatorial bounds and
enumeration},
journal = {Theor. Comput. Sci.},
volume = {487},
pages = {82--94},
year = {2013}
}
@inproceedings{DBLP:conf/ciac/GolovachHKR13,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Arash Rafiey},
title = {Cliques and Clubs},
booktitle = {{CIAC}},
series = {Lecture Notes in Computer Science},
volume = {7878},
pages = {276--287},
publisher = {Springer},
year = {2013}
}
@inproceedings{DBLP:conf/icalp/GolovachHKV13,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Yngve Villanger},
title = {An Incremental Polynomial Time Algorithm to Enumerate All Minimal
Edge Dominating Sets},
booktitle = {{ICALP} {(1)}},
series = {Lecture Notes in Computer Science},
volume = {7965},
pages = {485--496},
publisher = {Springer},
year = {2013}
}
@inproceedings{DBLP:conf/iwoca/ChapelleCCKLP13,
author = {Mathieu Chapelle and
Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Dieter Kratsch and
Mathieu Liedloff and
Anthony Perez},
title = {Exact Algorithms for Weak Roman Domination},
booktitle = {{IWOCA}},
series = {Lecture Notes in Computer Science},
volume = {8288},
pages = {81--93},
publisher = {Springer},
year = {2013}
}
@inproceedings{DBLP:conf/iwpec/KratschK13,
author = {Dieter Kratsch and
Stefan Kratsch},
title = {The Jump Number Problem: Exact and Parameterized},
booktitle = {{IPEC}},
series = {Lecture Notes in Computer Science},
volume = {8246},
pages = {230--242},
publisher = {Springer},
year = {2013}
}
@inproceedings{DBLP:conf/wg/CochefertCGKP13,
author = {Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma},
title = {Sparse Square Roots},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {8165},
pages = {177--188},
publisher = {Springer},
year = {2013}
}
@article{DBLP:journals/corr/CochefertCGKP13,
author = {Manfred Cochefert and
Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma},
title = {Parameterized Algorithms for Finding Square Roots},
journal = {CoRR},
volume = {abs/1310.5469},
year = {2013}
}
@article{DBLP:journals/algorithmica/GaspersKL12,
author = {Serge Gaspers and
Dieter Kratsch and
Mathieu Liedloff},
title = {On Independent Sets and Bicliques in Graphs},
journal = {Algorithmica},
volume = {62},
number = {3-4},
pages = {637--658},
year = {2012}
}
@article{DBLP:journals/ipl/CouturierK12,
author = {Jean{-}Fran{\c{c}}ois Couturier and
Dieter Kratsch},
title = {Bicolored independent sets and bicliques},
journal = {Inf. Process. Lett.},
volume = {112},
number = {8-9},
pages = {329--334},
year = {2012}
}
@article{DBLP:journals/jda/CouturierGKP12,
author = {Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma},
title = {On the parameterized complexity of coloring graphs in the absence
of a linear forest},
journal = {J. Discrete Algorithms},
volume = {15},
pages = {56--62},
year = {2012}
}
@article{DBLP:journals/mst/BodlaenderFKKT12,
author = {Hans L. Bodlaender and
Fedor V. Fomin and
Arie M. C. A. Koster and
Dieter Kratsch and
Dimitrios M. Thilikos},
title = {A Note on Exact Algorithms for Vertex Ordering Problems on Graphs},
journal = {Theory Comput. Syst.},
volume = {50},
number = {3},
pages = {420--432},
year = {2012}
}
@article{DBLP:journals/talg/BodlaenderFKKT12,
author = {Hans L. Bodlaender and
Fedor V. Fomin and
Arie M. C. A. Koster and
Dieter Kratsch and
Dimitrios M. Thilikos},
title = {On exact algorithms for treewidth},
journal = {{ACM} Trans. Algorithms},
volume = {9},
number = {1},
pages = {12:1--12:23},
year = {2012}
}
@inproceedings{DBLP:conf/esa/KratschM12,
author = {Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Colouring AT-Free Graphs},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {7501},
pages = {707--718},
publisher = {Springer},
year = {2012}
}
@inproceedings{DBLP:conf/isaac/GolovachKP12,
author = {Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma},
title = {Detecting Induced Minors in AT-Free Graphs},
booktitle = {{ISAAC}},
series = {Lecture Notes in Computer Science},
volume = {7676},
pages = {495--505},
publisher = {Springer},
year = {2012}
}
@inproceedings{DBLP:conf/iwpec/GolovachHKS12,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Reza Saei},
title = {An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs},
booktitle = {{IPEC}},
series = {Lecture Notes in Computer Science},
volume = {7535},
pages = {85--96},
publisher = {Springer},
year = {2012}
}
@inproceedings{DBLP:conf/sofsem/CouturierHHK12,
author = {Jean{-}Fran{\c{c}}ois Couturier and
Pinar Heggernes and
Pim van 't Hof and
Dieter Kratsch},
title = {Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and
Enumeration},
booktitle = {{SOFSEM}},
series = {Lecture Notes in Computer Science},
volume = {7147},
pages = {202--213},
publisher = {Springer},
year = {2012}
}
@article{DBLP:journals/corr/abs-1208-5345,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Yngve Villanger},
title = {Generating All Minimal Edge Dominating Sets with Incremental-Polynomial
Delay},
journal = {CoRR},
volume = {abs/1208.5345},
year = {2012}
}
@article{DBLP:journals/algorithmica/HavetKKKL11,
author = {Fr{\'{e}}d{\'{e}}ric Havet and
Martin Klazar and
Jan Kratochv{\'{\i}}l and
Dieter Kratsch and
Mathieu Liedloff},
title = {Exact Algorithms for \emph{L}(2, 1)-Labeling of Graphs},
journal = {Algorithmica},
volume = {59},
number = {2},
pages = {169--194},
year = {2011}
}
@article{DBLP:journals/algorithmica/FominGKKL11,
author = {Fedor V. Fomin and
Petr A. Golovach and
Jan Kratochv{\'{\i}}l and
Dieter Kratsch and
Mathieu Liedloff},
title = {Branch and Recharge: Exact Algorithms for Generalized Domination},
journal = {Algorithmica},
volume = {61},
number = {2},
pages = {252--273},
year = {2011}
}
@article{DBLP:journals/jda/Binkele-RaibleBCFKKLLPRW11,
author = {Daniel Binkele{-}Raible and
Ljiljana Brankovic and
Marek Cygan and
Henning Fernau and
Joachim Kneis and
Dieter Kratsch and
Alexander Langer and
Mathieu Liedloff and
Marcin Pilipczuk and
Peter Rossmanith and
Jakub Onufry Wojtaszczyk},
title = {Breaking the 2\({}^{\mbox{n}}\)-barrier for Irredundance: Two lines
of attack},
journal = {J. Discrete Algorithms},
volume = {9},
number = {3},
pages = {214--230},
year = {2011}
}
@article{DBLP:journals/tcs/FernauKKLLRR11,
author = {Henning Fernau and
Joachim Kneis and
Dieter Kratsch and
Alexander Langer and
Mathieu Liedloff and
Daniel Raible and
Peter Rossmanith},
title = {An exact algorithm for the Maximum Leaf Spanning Tree problem},
journal = {Theor. Comput. Sci.},
volume = {412},
number = {45},
pages = {6290--6302},
year = {2011}
}
@article{DBLP:journals/tcs/GolovachHKLMS11,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Daniel Lokshtanov and
Daniel Meister and
Saket Saurabh},
title = {Bandwidth on AT-free graphs},
journal = {Theor. Comput. Sci.},
volume = {412},
number = {50},
pages = {7001--7008},
year = {2011}
}
@inproceedings{DBLP:conf/colognetwente/CouturierK11,
author = {Jean{-}Fran{\c{c}}ois Couturier and
Dieter Kratsch},
title = {Bicolored independent sets and bicliques},
booktitle = {{CTW}},
pages = {130--133},
year = {2011}
}
@inproceedings{DBLP:conf/wads/FominHKPV11,
author = {Fedor V. Fomin and
Pinar Heggernes and
Dieter Kratsch and
Charis Papadopoulos and
Yngve Villanger},
title = {Enumerating Minimal Subset Feedback Vertex Sets},
booktitle = {{WADS}},
series = {Lecture Notes in Computer Science},
volume = {6844},
pages = {399--410},
publisher = {Springer},
year = {2011}
}
@inproceedings{DBLP:conf/wg/BodlaenderK11,
author = {Hans L. Bodlaender and
Dieter Kratsch},
title = {Exact Algorithms for Kayles},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {6986},
pages = {59--70},
publisher = {Springer},
year = {2011}
}
@inproceedings{DBLP:conf/wg/CouturierGKP11,
author = {Jean{-}Fran{\c{c}}ois Couturier and
Petr A. Golovach and
Dieter Kratsch and
Dani{\"{e}}l Paulusma},
title = {List Coloring in the Absence of a Linear Forest},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {6986},
pages = {119--130},
publisher = {Springer},
year = {2011}
}
@book{DBLP:series/txtcs/FominK10,
author = {Fedor V. Fomin and
Dieter Kratsch},
title = {Exact Exponential Algorithms},
series = {Texts in Theoretical Computer Science. An {EATCS} Series},
publisher = {Springer},
year = {2010}
}
@article{DBLP:journals/ipl/FominGGKS10,
author = {Fedor V. Fomin and
Serge Gaspers and
Petr A. Golovach and
Dieter Kratsch and
Saket Saurabh},
title = {Parameterized algorithm for eternal vertex cover},
journal = {Inf. Process. Lett.},
volume = {110},
number = {16},
pages = {702--706},
year = {2010}
}
@article{DBLP:journals/tcs/FominGKLS10,
author = {Fedor V. Fomin and
Serge Gaspers and
Dieter Kratsch and
Mathieu Liedloff and
Saket Saurabh},
title = {Iterative compression and exact algorithms},
journal = {Theor. Comput. Sci.},
volume = {411},
number = {7-9},
pages = {1045--1053},
year = {2010}
}
@inproceedings{DBLP:conf/ciac/Binkele-RaibleBFKKLLR10,
author = {Daniel Binkele{-}Raible and
Ljiljana Brankovic and
Henning Fernau and
Joachim Kneis and
Dieter Kratsch and
Alexander Langer and
Mathieu Liedloff and
Peter Rossmanith},
title = {A Parameterized Route to Exact Puzzles: Breaking the 2\({}^{\mbox{\emph{n}}}\)-Barrier
for Irredundance},
booktitle = {{CIAC}},
series = {Lecture Notes in Computer Science},
volume = {6078},
pages = {311--322},
publisher = {Springer},
year = {2010}
}
@inproceedings{DBLP:conf/swat/HeggernesKLRS10,
author = {Pinar Heggernes and
Dieter Kratsch and
Daniel Lokshtanov and
Venkatesh Raman and
Saket Saurabh},
title = {Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle
Stabbing},
booktitle = {{SWAT}},
series = {Lecture Notes in Computer Science},
volume = {6139},
pages = {334--345},
publisher = {Springer},
year = {2010}
}
@inproceedings{DBLP:conf/wg/GolovachKC10,
author = {Petr A. Golovach and
Dieter Kratsch and
Jean{-}Fran{\c{c}}ois Couturier},
title = {Colorings with Few Colors: Counting, Enumeration and Combinatorial
Bounds},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {6410},
pages = {39--50},
year = {2010}
}
@proceedings{DBLP:conf/dagstuhl/2010P10441,
editor = {Thore Husfeldt and
Dieter Kratsch and
Ramamohan Paturi and
Gregory B. Sorkin},
title = {Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010},
series = {Dagstuhl Seminar Proceedings},
volume = {10441},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2010}
}
@inproceedings{DBLP:conf/dagstuhl/HusfeldtKPS10,
author = {Thore Husfeldt and
Dieter Kratsch and
Ramamohan Paturi and
Gregory B. Sorkin},
title = {10441 Abstracts Collection - Exact Complexity of NP-hard Problems},
booktitle = {Exact Complexity of NP-hard Problems},
series = {Dagstuhl Seminar Proceedings},
volume = {10441},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2010}
}
@article{DBLP:journals/dm/KratschM09,
author = {Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {On a property of minimal triangulations},
journal = {Discret. Math.},
volume = {309},
number = {6},
pages = {1724--1729},
year = {2009}
}
@article{DBLP:journals/ipl/FominGKKL09,
author = {Fedor V. Fomin and
Petr A. Golovach and
Jan Kratochv{\'{\i}}l and
Dieter Kratsch and
Mathieu Liedloff},
title = {Sort and Search: Exact algorithms for generalized domination},
journal = {Inf. Process. Lett.},
volume = {109},
number = {14},
pages = {795--798},
year = {2009}
}
@article{DBLP:journals/jacm/FominGK09,
author = {Fedor V. Fomin and
Fabrizio Grandoni and
Dieter Kratsch},
title = {A measure {\&} conquer approach for the analysis of exact algorithms},
journal = {J. {ACM}},
volume = {56},
number = {5},
pages = {25:1--25:32},
year = {2009}
}
@article{DBLP:journals/jda/HeggernesKM09,
author = {Pinar Heggernes and
Dieter Kratsch and
Daniel Meister},
title = {Bandwidth of bipartite permutation graphs in polynomial time},
journal = {J. Discrete Algorithms},
volume = {7},
number = {4},
pages = {533--544},
year = {2009}
}
@article{DBLP:journals/talg/GaspersKLT09,
author = {Serge Gaspers and
Dieter Kratsch and
Mathieu Liedloff and
Ioan Todinca},
title = {Exponential time algorithms for the minimum dominating set problem
on some graph classes},
journal = {{ACM} Trans. Algorithms},
volume = {6},
number = {1},
pages = {9:1--9:21},
year = {2009}
}
@inproceedings{DBLP:conf/cocoon/KanjK09,
author = {Iyad A. Kanj and
Dieter Kratsch},
title = {Convex Recoloring Revisited: Complexity and Exact Algorithms},
booktitle = {{COCOON}},
series = {Lecture Notes in Computer Science},
volume = {5609},
pages = {388--397},
publisher = {Springer},
year = {2009}
}
@inproceedings{DBLP:conf/colognetwente/FernauGKLR09,
author = {Henning Fernau and
Serge Gaspers and
Dieter Kratsch and
Mathieu Liedloff and
Daniel Raible},
title = {Exact Exponential-Time Algorithms for Finding Bicliques in a Graph},
booktitle = {{CTW}},
pages = {205--209},
year = {2009}
}
@inproceedings{DBLP:conf/isaac/GolovachHKLMS09,
author = {Petr A. Golovach and
Pinar Heggernes and
Dieter Kratsch and
Daniel Lokshtanov and
Daniel Meister and
Saket Saurabh},
title = {Bandwidth on AT-Free Graphs},
booktitle = {{ISAAC}},
series = {Lecture Notes in Computer Science},
volume = {5878},
pages = {573--582},
publisher = {Springer},
year = {2009}
}
@inproceedings{DBLP:conf/iwoca/BroersmaKW09,
author = {Hajo Broersma and
Dieter Kratsch and
Gerhard J. Woeginger},
title = {Fully Decomposable Split Graphs},
booktitle = {{IWOCA}},
series = {Lecture Notes in Computer Science},
volume = {5874},
pages = {105--112},
publisher = {Springer},
year = {2009}
}
@inproceedings{DBLP:conf/iwpec/FernauKKLLRR09,
author = {Henning Fernau and
Joachim Kneis and
Dieter Kratsch and
Alexander Langer and
Mathieu Liedloff and
Daniel Raible and
Peter Rossmanith},
title = {An Exact Algorithm for the Maximum Leaf Spanning Tree Problem},
booktitle = {{IWPEC}},
series = {Lecture Notes in Computer Science},
volume = {5917},
pages = {161--172},
publisher = {Springer},
year = {2009}
}
@article{DBLP:journals/corr/abs-0909-4224,
author = {Ljiljana Brankovic and
Henning Fernau and
Joachim Kneis and
Dieter Kratsch and
Alexander Langer and
Mathieu Liedloff and
Daniel Raible and
Peter Rossmanith},
title = {Breaking the 2{\^{}}n-Barrier for Irredundance: {A} Parameterized
Route to Solving Exact Puzzles},
journal = {CoRR},
volume = {abs/0909.4224},
year = {2009}
}
@article{DBLP:journals/algorithmica/FominGK08,
author = {Fedor V. Fomin and
Fabrizio Grandoni and
Dieter Kratsch},
title = {Solving Connected Dominating Set Faster than 2\({}^{\mbox{ \emph{n}
}}\)},
journal = {Algorithmica},
volume = {52},
number = {2},
pages = {153--166},
year = {2008}
}
@article{DBLP:journals/dam/KratschMT08,
author = {Dieter Kratsch and
Haiko M{\"{u}}ller and
Ioan Todinca},
title = {Feedback vertex set on AT-free graphs},
journal = {Discret. Appl. Math.},
volume = {156},
number = {10},
pages = {1936--1947},
year = {2008}
}
@article{DBLP:journals/dm/KratschSS08,
author = {Dieter Kratsch and
Jeremy P. Spinrad and
R. Sritharan},
title = {A new characterization of HH-free graphs},
journal = {Discret. Math.},
volume = {308},
number = {20},
pages = {4833--4835},
year = {2008}
}
@article{DBLP:journals/siamcomp/FominKTV08,
author = {Fedor V. Fomin and
Dieter Kratsch and
Ioan Todinca and
Yngve Villanger},
title = {Exact Algorithms for Treewidth and Minimum Fill-In},
journal = {{SIAM} J. Comput.},
volume = {38},
number = {3},
pages = {1058--1079},
year = {2008}
}
@inproceedings{DBLP:conf/esa/FominGK08,
author = {Fedor V. Fomin and
Fabrizio Grandoni and
Dieter Kratsch},
title = {Faster Steiner Tree Computation in Polynomial-Space},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {5193},
pages = {430--441},
publisher = {Springer},
year = {2008}
}
@inproceedings{DBLP:conf/latin/HeggernesKM08,
author = {Pinar Heggernes and
Dieter Kratsch and
Daniel Meister},
title = {Bandwidth of Bipartite Permutation Graphs in Polynomial Time},
booktitle = {{LATIN}},
series = {Lecture Notes in Computer Science},
volume = {4957},
pages = {216--227},
publisher = {Springer},
year = {2008}
}
@inproceedings{DBLP:conf/mfcs/FominGKLS08,
author = {Fedor V. Fomin and
Serge Gaspers and
Dieter Kratsch and
Mathieu Liedloff and
Saket Saurabh},
title = {Iterative Compression and Exact Algorithms},
booktitle = {{MFCS}},
series = {Lecture Notes in Computer Science},
volume = {5162},
pages = {335--346},
publisher = {Springer},
year = {2008}
}
@inproceedings{DBLP:conf/wg/GaspersKL08,
author = {Serge Gaspers and
Dieter Kratsch and
Mathieu Liedloff},
title = {On Independent Sets and Bicliques in Graphs},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {5344},
pages = {171--182},
year = {2008}
}
@proceedings{DBLP:conf/dagstuhl/2008P8431,
editor = {Fedor V. Fomin and
Kazuo Iwama and
Dieter Kratsch},
title = {Moderately Exponential Time Algorithms, 19.10. - 24.10.2008},
series = {Dagstuhl Seminar Proceedings},
volume = {08431},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008}
}
@incollection{DBLP:reference/algo/Kratsch08,
author = {Dieter Kratsch and
Fedor V. Fomin and
Fabrizio Grandoni},
title = {Exact Algorithms for Dominating Set},
booktitle = {Encyclopedia of Algorithms},
publisher = {Springer},
year = {2008}
}
@inproceedings{DBLP:conf/dagstuhl/FominIK08,
author = {Fedor V. Fomin and
Kazuo Iwama and
Dieter Kratsch},
title = {08431 Abstracts Collection - Moderately Exponential Time Algorithms},
booktitle = {Moderately Exponential Time Algorithms},
series = {Dagstuhl Seminar Proceedings},
volume = {08431},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008}
}
@inproceedings{DBLP:conf/dagstuhl/FominIK08a,
author = {Fedor V. Fomin and
Kazuo Iwama and
Dieter Kratsch},
title = {08431 Executive Summary - Moderately Exponential Time Algorithms},
booktitle = {Moderately Exponential Time Algorithms},
series = {Dagstuhl Seminar Proceedings},
volume = {08431},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008}
}
@inproceedings{DBLP:conf/dagstuhl/FominIKKKKORW08,
author = {Fedor V. Fomin and
Kazuo Iwama and
Dieter Kratsch and
Petteri Kaski and
Mikko Koivisto and
Lukasz Kowalik and
Yoshio Okamoto and
Johan M. M. van Rooij and
Ryan Williams},
title = {08431 Open Problems - Moderately Exponential Time Algorithms},
booktitle = {Moderately Exponential Time Algorithms},
series = {Dagstuhl Seminar Proceedings},
volume = {08431},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008}
}
@article{DBLP:journals/mst/FominHK07,
author = {Fedor V. Fomin and
Pinar Heggernes and
Dieter Kratsch},
title = {Exact Algorithms for Graph Homomorphisms},
journal = {Theory Comput. Syst.},
volume = {41},
number = {2},
pages = {381--393},
year = {2007}
}
@article{DBLP:journals/njc/HeggernesK07,
author = {Pinar Heggernes and
Dieter Kratsch},
title = {Linear-time certifying recognition algorithms and forbidden induced
subgraphs},
journal = {Nord. J. Comput.},
volume = {14},
number = {1-2},
pages = {87--108},
year = {2007}
}
@article{DBLP:journals/tcs/KratschL07,
author = {Dieter Kratsch and
Mathieu Liedloff},
title = {An exact algorithm for the minimum dominating clique problem},
journal = {Theor. Comput. Sci.},
volume = {385},
number = {1-3},
pages = {226--240},
year = {2007}
}
@inproceedings{DBLP:conf/mfcs/KratochvilKL07,
author = {Jan Kratochv{\'{\i}}l and
Dieter Kratsch and
Mathieu Liedloff},
title = {Exact Algorithms for \emph{L} (2, 1)-Labeling of Graphs},
booktitle = {{MFCS}},
series = {Lecture Notes in Computer Science},
volume = {4708},
pages = {513--524},
publisher = {Springer},
year = {2007}
}
@inproceedings{DBLP:conf/wads/FominGKKL07,
author = {Fedor V. Fomin and
Petr A. Golovach and
Jan Kratochv{\'{\i}}l and
Dieter Kratsch and
Mathieu Liedloff},
title = {Branch and Recharge: Exact Algorithms for Generalized Domination},
booktitle = {{WADS}},
series = {Lecture Notes in Computer Science},
volume = {4619},
pages = {507--518},
publisher = {Springer},
year = {2007}
}
@proceedings{DBLP:conf/dagstuhl/2007P7211,
editor = {Andreas Brandst{\"{a}}dt and
Klaus Jansen and
Dieter Kratsch and
Jeremy P. Spinrad},
title = {Exact, Approximative, Robust and Certifying Algorithms on Particular
Graph Classes, 20.05. - 25.05.2007},
series = {Dagstuhl Seminar Proceedings},
volume = {07211},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2007}
}
@proceedings{DBLP:conf/wg/2007,
editor = {Andreas Brandst{\"{a}}dt and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Graph-Theoretic Concepts in Computer Science, 33rd International Workshop,
{WG} 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers},
series = {Lecture Notes in Computer Science},
volume = {4769},
publisher = {Springer},
year = {2007}
}
@inproceedings{DBLP:conf/dagstuhl/BrandstadtJKS07,
author = {Andreas Brandst{\"{a}}dt and
Klaus Jansen and
Dieter Kratsch and
Jeremy P. Spinrad},
title = {07211 Abstracts Collection - Exact, Approximative, Robust and Certifying
Algorithms on Particular Graph Classes},
booktitle = {Exact, Approximative, Robust and Certifying Algorithms on Particular
Graph Classes},
series = {Dagstuhl Seminar Proceedings},
volume = {07211},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2007}
}
@article{DBLP:journals/dam/KloksKLL06,
author = {Ton Kloks and
Dieter Kratsch and
Chuan{-}Min Lee and
Jiping Liu},
title = {Improved bottleneck domination algorithms},
journal = {Discret. Appl. Math.},
volume = {154},
number = {11},
pages = {1578--1592},
year = {2006}
}
@article{DBLP:journals/dm/KratschS06,
author = {Dieter Kratsch and
Jeremy P. Spinrad},
title = {Minimal fill in O(\emph{n}\({}^{\mbox{2.69}}\)) time},
journal = {Discret. Math.},
volume = {306},
number = {3},
pages = {366--371},
year = {2006}
}
@article{DBLP:journals/siamcomp/KratschS06,
author = {Dieter Kratsch and
Jeremy P. Spinrad},
title = {Between O(nm) and O(n\({}^{\mbox{alpha}}\))},
journal = {{SIAM} J. Comput.},
volume = {36},
number = {2},
pages = {310--325},
year = {2006}
}
@article{DBLP:journals/siamcomp/KratschMMS06,
author = {Dieter Kratsch and
Ross M. McConnell and
Kurt Mehlhorn and
Jeremy P. Spinrad},
title = {Certifying Algorithms for Recognizing Interval Graphs and Permutation
Graphs},
journal = {{SIAM} J. Comput.},
volume = {36},
number = {2},
pages = {326--353},
year = {2006}
}
@inproceedings{DBLP:conf/esa/BodlaenderFKKT06,
author = {Hans L. Bodlaender and
Fedor V. Fomin and
Arie M. C. A. Koster and
Dieter Kratsch and
Dimitrios M. Thilikos},
title = {On Exact Algorithms for Treewidth},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {4168},
pages = {672--683},
publisher = {Springer},
year = {2006}
}
@inproceedings{DBLP:conf/fsttcs/FominGK06,
author = {Fedor V. Fomin and
Fabrizio Grandoni and
Dieter Kratsch},
title = {Solving Connected Dominating Set Faster Than 2\({}^{\mbox{\emph{n}}}\)},
booktitle = {{FSTTCS}},
series = {Lecture Notes in Computer Science},
volume = {4337},
pages = {152--163},
publisher = {Springer},
year = {2006}
}
@inproceedings{DBLP:conf/iwpec/KratschL06,
author = {Dieter Kratsch and
Mathieu Liedloff},
title = {An Exact Algorithm for the Minimum Dominating Clique Problem},
booktitle = {{IWPEC}},
series = {Lecture Notes in Computer Science},
volume = {4169},
pages = {130--141},
publisher = {Springer},
year = {2006}
}
@inproceedings{DBLP:conf/mfcs/CohenFHKK06,
author = {Johanne Cohen and
Fedor V. Fomin and
Pinar Heggernes and
Dieter Kratsch and
Gregory Kucherov},
title = {Optimal Linear Arrangement of Interval Graphs},
booktitle = {{MFCS}},
series = {Lecture Notes in Computer Science},
volume = {4162},
pages = {267--279},
publisher = {Springer},
year = {2006}
}
@inproceedings{DBLP:conf/soda/FominGK06,
author = {Fedor V. Fomin and
Fabrizio Grandoni and
Dieter Kratsch},
title = {Measure and conquer: a simple O(2\({}^{\mbox{0.288\emph{n}}}\)) independent
set algorithm},
booktitle = {{SODA}},
pages = {18--25},
publisher = {{ACM} Press},
year = {2006}
}
@inproceedings{DBLP:conf/swat/GaspersKL06,
author = {Serge Gaspers and
Dieter Kratsch and
Mathieu Liedloff},
title = {Exponential Time Algorithms for the Minimum Dominating Set Problem
on Some Graph Classes},
booktitle = {{SWAT}},
series = {Lecture Notes in Computer Science},
volume = {4059},
pages = {148--159},
publisher = {Springer},
year = {2006}
}
@article{DBLP:journals/dam/BrandstadtK05,
author = {Andreas Brandst{\"{a}}dt and
Dieter Kratsch},
title = {On the structure of (\emph{P}\({}_{\mbox{5}}\), gem)-free graphs},
journal = {Discret. Appl. Math.},
volume = {145},
number = {2},
pages = {155--166},
year = {2005}
}
@article{DBLP:journals/eatcs/FominGK05,
author = {Fedor V. Fomin and
Fabrizio Grandoni and
Dieter Kratsch},
title = {Some New Techniques in Design and Analysis of Exact (Exponential)
Algorithms},
journal = {Bull. {EATCS}},
volume = {87},
pages = {47--77},
year = {2005}
}
@article{DBLP:journals/tcs/BodlaenderBKRS05,
author = {Hans L. Bodlaender and
Andreas Brandst{\"{a}}dt and
Dieter Kratsch and
Micha{\"{e}}l Rao and
Jeremy P. Spinrad},
title = {On algorithms for (\emph{P}\({}_{\mbox{5}}\), gem)-free graphs},
journal = {Theor. Comput. Sci.},
volume = {349},
number = {1},
pages = {2--21},
year = {2005}
}
@inproceedings{DBLP:conf/cocoon/ChangKKLP05,
author = {Maw{-}Shang Chang and
Ton Kloks and
Dieter Kratsch and
Jiping Liu and
Sheng{-}Lung Peng},
title = {On the Recognition of Probe Graphs of Some Self-Complementary Classes
of Perfect Graphs},
booktitle = {{COCOON}},
series = {Lecture Notes in Computer Science},
volume = {3595},
pages = {808--817},
publisher = {Springer},
year = {2005}
}
@inproceedings{DBLP:conf/fct/FominHK05,
author = {Fedor V. Fomin and
Pinar Heggernes and
Dieter Kratsch},
title = {Exact Algorithms for Graph Homomorphisms},
booktitle = {{FCT}},
series = {Lecture Notes in Computer Science},
volume = {3623},
pages = {161--171},
publisher = {Springer},
year = {2005}
}
@inproceedings{DBLP:conf/icalp/FominGK05,
author = {Fedor V. Fomin and
Fabrizio Grandoni and
Dieter Kratsch},
title = {Measure and Conquer: Domination - {A} Case Study},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {3580},
pages = {191--203},
publisher = {Springer},
year = {2005}
}
@proceedings{DBLP:conf/wg/2005,
editor = {Dieter Kratsch},
title = {Graph-Theoretic Concepts in Computer Science, 31st International Workshop,
{WG} 2005, Metz, France, June 23-25, 2005, Revised Selected Papers},
series = {Lecture Notes in Computer Science},
volume = {3787},
publisher = {Springer},
year = {2005}
}
@article{DBLP:journals/dam/FominKM04,
author = {Fedor V. Fomin and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Algorithms for graphs with small octopus},
journal = {Discret. Appl. Math.},
volume = {134},
number = {1-3},
pages = {105--128},
year = {2004}
}
@article{DBLP:journals/dam/BouchitteKMT04,
author = {Vincent Bouchitt{\'{e}} and
Dieter Kratsch and
Haiko M{\"{u}}ller and
Ioan Todinca},
title = {On treewidth approximations},
journal = {Discret. Appl. Math.},
volume = {136},
number = {2-3},
pages = {183--196},
year = {2004}
}
@inproceedings{DBLP:conf/icalp/FominKT04,
author = {Fedor V. Fomin and
Dieter Kratsch and
Ioan Todinca},
title = {Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {3142},
pages = {568--580},
publisher = {Springer},
year = {2004}
}
@inproceedings{DBLP:conf/wg/FominKW04,
author = {Fedor V. Fomin and
Dieter Kratsch and
Gerhard J. Woeginger},
title = {Exact (Exponential) Algorithms for the Dominating Set Problem},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {3353},
pages = {245--256},
publisher = {Springer},
year = {2004}
}
@article{DBLP:journals/dam/FominKM03,
author = {Fedor V. Fomin and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {On the Domination Search Number},
journal = {Discret. Appl. Math.},
volume = {127},
number = {3},
pages = {565--580},
year = {2003}
}
@inproceedings{DBLP:conf/fct/BodlaenderBKRS03,
author = {Hans L. Bodlaender and
Andreas Brandst{\"{a}}dt and
Dieter Kratsch and
Micha{\"{e}}l Rao and
Jeremy P. Spinrad},
title = {Linear Time Algorithms for Some NP-Complete Problems on (P\({}_{\mbox{5}}\),
Gem)-Free Graphs},
booktitle = {{FCT}},
series = {Lecture Notes in Computer Science},
volume = {2751},
pages = {61--72},
publisher = {Springer},
year = {2003}
}
@inproceedings{DBLP:conf/soda/KratschMMS03,
author = {Dieter Kratsch and
Ross M. McConnell and
Kurt Mehlhorn and
Jeremy P. Spinrad},
title = {Certifying algorithms for recognizing interval graphs and permutation
graphs},
booktitle = {{SODA}},
pages = {158--167},
publisher = {{ACM/SIAM}},
year = {2003}
}
@inproceedings{DBLP:conf/soda/KratschS03,
author = {Dieter Kratsch and
Jeremy P. Spinrad},
title = {Between O(nm) and O(n alpha)},
booktitle = {{SODA}},
pages = {709--716},
publisher = {{ACM/SIAM}},
year = {2003}
}
@inproceedings{DBLP:conf/wg/KratschMT03,
author = {Dieter Kratsch and
Haiko M{\"{u}}ller and
Ioan Todinca},
title = {Feedback Vertex Set and Longest Induced Path on AT-Free Graphs},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {2880},
pages = {309--321},
publisher = {Springer},
year = {2003}
}
@article{DBLP:journals/algorithmica/BroersmaKKM02,
author = {Hajo Broersma and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {A Generalization of AT-Free Graphs and a Generic Algorithm for Solving
Triangulation Problems},
journal = {Algorithmica},
volume = {32},
number = {4},
pages = {594--610},
year = {2002}
}
@article{DBLP:journals/dam/HempelK02,
author = {Harald Hempel and
Dieter Kratsch},
title = {On claw-free asteroidal triple-free graphs},
journal = {Discret. Appl. Math.},
volume = {121},
number = {1-3},
pages = {155--180},
year = {2002}
}
@article{DBLP:journals/ipl/FominKN02,
author = {Fedor V. Fomin and
Dieter Kratsch and
Jean{-}Christophe Novelli},
title = {Approximating minimum cocolorings},
journal = {Inf. Process. Lett.},
volume = {84},
number = {5},
pages = {285--290},
year = {2002}
}
@article{DBLP:journals/jal/BodlaenderK02,
author = {Hans L. Bodlaender and
Dieter Kratsch},
title = {Kayles and Nimbers},
journal = {J. Algorithms},
volume = {43},
number = {1},
pages = {106--119},
year = {2002}
}
@article{DBLP:journals/siamdm/DeogunK02,
author = {Jitender S. Deogun and
Dieter Kratsch},
title = {Dominating Pair Graphs},
journal = {{SIAM} J. Discret. Math.},
volume = {15},
number = {3},
pages = {353--366},
year = {2002}
}
@article{DBLP:journals/siamdm/KratschS02,
author = {Dieter Kratsch and
Lorna Stewart},
title = {Approximating Bandwidth by Mixing Layouts of Interval Graphs},
journal = {{SIAM} J. Discret. Math.},
volume = {15},
number = {4},
pages = {435--449},
year = {2002}
}
@article{DBLP:journals/dm/BabelKKKMO01,
author = {Luitpold Babel and
Ton Kloks and
Jan Kratochv{\'{\i}}l and
Dieter Kratsch and
Haiko M{\"{u}}ller and
Stephan Olariu},
title = {Efficient algorithms for graphs with few \emph{P}\({}_{\mbox{4}}\)'s},
journal = {Discret. Math.},
volume = {235},
number = {1-3},
pages = {29--51},
year = {2001}
}
@article{DBLP:journals/endm/BouchitteKMT01,
author = {Vincent Bouchitt{\'{e}} and
Dieter Kratsch and
Haiko M{\"{u}}ller and
Ioan Todinca},
title = {On treewidth approximations},
journal = {Electron. Notes Discret. Math.},
volume = {8},
pages = {98--101},
year = {2001}
}
@article{DBLP:journals/gc/KloksKM01,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {On the Structure of Graphs with Bounded Asteroidal Number},
journal = {Graphs Comb.},
volume = {17},
number = {2},
pages = {295--306},
year = {2001}
}
@inproceedings{DBLP:conf/fct/FominKN01,
author = {Fedor V. Fomin and
Dieter Kratsch and
Jean{-}Christophe Novelli},
title = {Approximating Minimum Cocolourings},
booktitle = {{FCT}},
series = {Lecture Notes in Computer Science},
volume = {2138},
pages = {118--125},
publisher = {Springer},
year = {2001}
}
@article{DBLP:journals/dam/Kratsch00,
author = {Dieter Kratsch},
title = {Domination and Total Domination on Asteroidal Triple-free Graphs},
journal = {Discret. Appl. Math.},
volume = {99},
number = {1-3},
pages = {111--123},
year = {2000}
}
@article{DBLP:journals/dam/BauerKKV00,
author = {Douglas Bauer and
Gyula Y. Katona and
Dieter Kratsch and
Henk Jan Veldman},
title = {Chordality and 2-factors in Tough Graphs},
journal = {Discret. Appl. Math.},
volume = {99},
number = {1-3},
pages = {323--329},
year = {2000}
}
@article{DBLP:journals/ipl/KloksKM00,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Finding and counting small induced subgraphs efficiently},
journal = {Inf. Process. Lett.},
volume = {74},
number = {3-4},
pages = {115--121},
year = {2000}
}
@article{DBLP:journals/networks/BroersmaKTHKKM00,
author = {Hajo Broersma and
Otto R. Koppius and
Hilde Tuinstra and
Andreas Huck and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Degree-preserving trees},
journal = {Networks},
volume = {35},
number = {1},
pages = {26--39},
year = {2000}
}
@inproceedings{DBLP:conf/wg/FominKM00,
author = {Fedor V. Fomin and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {On the Domination Search Number},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {1928},
pages = {161--171},
publisher = {Springer},
year = {2000}
}
@inproceedings{DBLP:conf/wg/KloksKBM00,
author = {Ton Kloks and
Dieter Kratsch and
Yvan Le Borgne and
Haiko M{\"{u}}ller},
title = {Bandwidth of Split and Circular Permutation Graphs},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {1928},
pages = {243--254},
publisher = {Springer},
year = {2000}
}
@article{DBLP:journals/dam/DeogunKKM99,
author = {Jitender S. Deogun and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {On the Vertex Ranking Problem for Trapezoid, Circular-arc and Other
Graphs},
journal = {Discret. Appl. Math.},
volume = {98},
number = {1-2},
pages = {39--63},
year = {1999}
}
@article{DBLP:journals/endm/KloksKM99,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {On the structure of graphs with bounded asteroidal number},
journal = {Electron. Notes Discret. Math.},
volume = {3},
pages = {94},
year = {1999}
}
@article{DBLP:journals/endm/KratschS99,
author = {Dieter Kratsch and
Lorna Stewart},
title = {Approximating Bandwidth by Mixing Layouts of Interval Graphs},
journal = {Electron. Notes Discret. Math.},
volume = {3},
pages = {106--109},
year = {1999}
}
@article{DBLP:journals/jal/KloksKM99,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Approximating the Bandwidth for Asteroidal Triple-Free Graphs},
journal = {J. Algorithms},
volume = {32},
number = {1},
pages = {41--57},
year = {1999}
}
@article{DBLP:journals/siamdm/BroersmaKKM99,
author = {Hajo Broersma and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Independent Sets in Asteroidal Triple-Free Graphs},
journal = {{SIAM} J. Discret. Math.},
volume = {12},
number = {2},
pages = {276--287},
year = {1999}
}
@inproceedings{DBLP:conf/stacs/KratschS99,
author = {Dieter Kratsch and
Lorna Stewart},
title = {Approximating Bandwidth by Mixing Layouts of Interval Graphs},
booktitle = {{STACS}},
series = {Lecture Notes in Computer Science},
volume = {1563},
pages = {248--258},
publisher = {Springer},
year = {1999}
}
@inproceedings{DBLP:conf/wg/HempelK99,
author = {Harald Hempel and
Dieter Kratsch},
title = {On Claw-Free Asteroidal Triple-Free Graphs},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {1665},
pages = {377--390},
publisher = {Springer},
year = {1999}
}
@article{DBLP:journals/dm/KratschR98,
author = {Dieter Kratsch and
Jean{-}Xavier Rampon},
title = {Tree-visibility orders},
journal = {Discret. Math.},
volume = {190},
number = {1-3},
pages = {163--175},
year = {1998}
}
@article{DBLP:journals/ipl/KloksKM98,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Bandwidth of Chain Graphs},
journal = {Inf. Process. Lett.},
volume = {68},
number = {6},
pages = {313--315},
year = {1998}
}
@article{DBLP:journals/jal/KloksKW98,
author = {Ton Kloks and
Dieter Kratsch and
C. K. Wong},
title = {Minimum Fill-in on Circle and Circular-Arc Graphs},
journal = {J. Algorithms},
volume = {28},
number = {2},
pages = {272--289},
year = {1998}
}
@article{DBLP:journals/jgaa/BodlaenderKKM98,
author = {Hans L. Bodlaender and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Treewidth and Minimum Fill-in on d-Trapezoid Graphs},
journal = {J. Graph Algorithms Appl.},
volume = {2},
number = {5},
pages = {1--23},
year = {1998}
}
@article{DBLP:journals/siamcomp/KloksK98,
author = {Ton Kloks and
Dieter Kratsch},
title = {Listing All Minimal Separators of a Graph},
journal = {{SIAM} J. Comput.},
volume = {27},
number = {3},
pages = {605--613},
year = {1998}
}
@article{DBLP:journals/siamdm/BodlaenderDJKKMT98,
author = {Hans L. Bodlaender and
Jitender S. Deogun and
Klaus Jansen and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller and
Zsolt Tuza},
title = {Rankings of Graphs},
journal = {{SIAM} J. Discret. Math.},
volume = {11},
number = {1},
pages = {168--181},
year = {1998}
}
@inproceedings{DBLP:conf/mfcs/BroersmaHKKKMT98,
author = {Hajo Broersma and
Andreas Huck and
Ton Kloks and
Otto R. Koppius and
Dieter Kratsch and
Haiko M{\"{u}}ller and
Hilde Tuinstra},
title = {Degree-Preserving Forests},
booktitle = {{MFCS}},
series = {Lecture Notes in Computer Science},
volume = {1450},
pages = {713--721},
publisher = {Springer},
year = {1998}
}
@inproceedings{DBLP:conf/wg/BroersmaKKM98,
author = {Hajo Broersma and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {A Generalization of AT-free Graphs and a Generic Algorithm for Solving
Treewidth, Minimum Fill-In and Vertex Ranking},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {1517},
pages = {88--99},
publisher = {Springer},
year = {1998}
}
@article{DBLP:journals/dam/KratschKM97,
author = {Dieter Kratsch and
Ton Kloks and
Haiko M{\"{u}}ller},
title = {Measuring the Vulnerability for Classes of Intersection Graphs},
journal = {Discret. Appl. Math.},
volume = {77},
number = {3},
pages = {259--270},
year = {1997}
}
@article{DBLP:journals/dm/DeogunKS97,
author = {Jitender S. Deogun and
Dieter Kratsch and
George Steiner},
title = {1-Tough cocomparability graphs are hamiltonian},
journal = {Discret. Math.},
volume = {170},
number = {1-3},
pages = {99--106},
year = {1997}
}
@article{DBLP:journals/ipl/DeogunKS97,
author = {Jitender S. Deogun and
Dieter Kratsch and
George Steiner},
title = {An Approximation Algorithm for Clustering Graphs with Dominating Diametral
Path},
journal = {Inf. Process. Lett.},
volume = {61},
number = {3},
pages = {121--127},
year = {1997}
}
@article{DBLP:journals/ipl/KratschS97,
author = {Dieter Kratsch and
Lorna Stewart},
title = {Total Domination and Transformation},
journal = {Inf. Process. Lett.},
volume = {63},
number = {3},
pages = {167--170},
year = {1997}
}
@article{DBLP:journals/tcs/KloksKS97,
author = {Ton Kloks and
Dieter Kratsch and
Jeremy P. Spinrad},
title = {On Treewidth and Minimum Fill-In of Asteroidal Triple-Free Graphs},
journal = {Theor. Comput. Sci.},
volume = {175},
number = {2},
pages = {309--335},
year = {1997}
}
@inproceedings{DBLP:conf/icalp/BroersmaKKM97,
author = {Hajo Broersma and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Independent Sets in Asteroidal Triple-Free Graphs},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {1256},
pages = {760--770},
publisher = {Springer},
year = {1997}
}
@inproceedings{DBLP:conf/wg/KloksKM97,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Asteroidal Sets in Graphs},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {1335},
pages = {229--241},
publisher = {Springer},
year = {1997}
}
@article{DBLP:journals/dm/KratschLM96,
author = {Dieter Kratsch and
Jen{\"{o}} Lehel and
Haiko M{\"{u}}ller},
title = {Toughness, hamiltonicity and split graphs},
journal = {Discret. Math.},
volume = {150},
number = {1-3},
pages = {231--245},
year = {1996}
}
@article{DBLP:journals/dm/KratschR96,
author = {Dieter Kratsch and
Jean{-}Xavier Rampon},
title = {Width two posets are reconstructible},
journal = {Discret. Math.},
volume = {162},
number = {1-3},
pages = {305--310},
year = {1996}
}
@article{DBLP:journals/jgt/GyarfasKLM96,
author = {Andr{\'{a}}s Gy{\'{a}}rf{\'{a}}s and
Dieter Kratsch and
Jen{\"{o}} Lehel and
Fr{\'{e}}d{\'{e}}ric Maffray},
title = {Minimal non-neighborhood-perfect graphs},
journal = {J. Graph Theory},
volume = {21},
number = {1},
pages = {55--66},
year = {1996}
}
@inproceedings{DBLP:conf/icalp/KloksKW96,
author = {Ton Kloks and
Dieter Kratsch and
C. K. Wong},
title = {Minimum Fill-In on Circle and Circular-Arc Graphs},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {1099},
pages = {256--267},
publisher = {Springer},
year = {1996}
}
@article{DBLP:journals/ipl/KloksK95,
author = {Ton Kloks and
Dieter Kratsch},
title = {Computing a Perfect Edge Without Vertex Elimination Ordering of a
Chordal Bipartite Graph},
journal = {Inf. Process. Lett.},
volume = {55},
number = {1},
pages = {11--16},
year = {1995}
}
@article{DBLP:journals/jal/KloksK95,
author = {Ton Kloks and
Dieter Kratsch},
title = {Treewidth of Chordal Bipartite Graphs},
journal = {J. Algorithms},
volume = {19},
number = {2},
pages = {266--281},
year = {1995}
}
@article{DBLP:journals/siamdm/BodlaenderKK95,
author = {Hans L. Bodlaender and
Ton Kloks and
Dieter Kratsch},
title = {Treewidth and Pathwidth of Permutation Graphs},
journal = {{SIAM} J. Discret. Math.},
volume = {8},
number = {4},
pages = {606--616},
year = {1995}
}
@inproceedings{DBLP:conf/esa/KloksKM95,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Approximating the Bandwidth for Asteroidal Triple-Free Graphs},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {979},
pages = {434--447},
publisher = {Springer},
year = {1995}
}
@inproceedings{DBLP:conf/wg/KloksKM95,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Finding and Counting Small Induced Subgraphs Efficiently},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {1017},
pages = {14--23},
publisher = {Springer},
year = {1995}
}
@inproceedings{DBLP:conf/wg/DeogunK95,
author = {Jitender S. Deogun and
Dieter Kratsch},
title = {Diametral Path Graphs},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {1017},
pages = {344--357},
publisher = {Springer},
year = {1995}
}
@article{DBLP:journals/dam/GimbelKS94,
author = {John G. Gimbel and
Dieter Kratsch and
Lorna Stewart},
title = {On Cocolourings and Cochromatic Numbers of Graphs},
journal = {Discret. Appl. Math.},
volume = {48},
number = {2},
pages = {111--127},
year = {1994}
}
@article{DBLP:journals/dm/KratschDL94,
author = {Dieter Kratsch and
Peter Damaschke and
Anna Lubiw},
title = {Dominating cliques in chordal graphs},
journal = {Discret. Math.},
volume = {128},
number = {1-3},
pages = {269--275},
year = {1994}
}
@article{DBLP:journals/mmor/KratschGVG94,
author = {Dieter Kratsch and
E. Godehardt and
S. Vo{\ss} and
O. Gascuel},
title = {Book reviews},
journal = {Math. Methods Oper. Res.},
volume = {40},
number = {1},
pages = {120--125},
year = {1994}
}
@article{DBLP:journals/mst/KratschH94,
author = {Dieter Kratsch and
Lane A. Hemaspaandra},
title = {On the Complexity of Graph Reconstruction},
journal = {Math. Syst. Theory},
volume = {27},
number = {3},
pages = {257--273},
year = {1994}
}
@inproceedings{DBLP:conf/esa/KloksBMK94,
author = {Ton Kloks and
Hans L. Bodlaender and
Haiko M{\"{u}}ller and
Dieter Kratsch},
title = {Erratum: Computing Treewidth and Minimum Fill-In: All You Need are
the Minimal Separators},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {855},
pages = {508},
publisher = {Springer},
year = {1994}
}
@inproceedings{DBLP:conf/stacs/DeogunKKM94,
author = {Jitender S. Deogun and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {On Vertex Ranking for Permutations and Other Graphs},
booktitle = {{STACS}},
series = {Lecture Notes in Computer Science},
volume = {775},
pages = {747--758},
publisher = {Springer},
year = {1994}
}
@inproceedings{DBLP:conf/stacs/KloksK94,
author = {Ton Kloks and
Dieter Kratsch},
title = {Finding All Minimal Separators of a Graph},
booktitle = {{STACS}},
series = {Lecture Notes in Computer Science},
volume = {775},
pages = {759--768},
publisher = {Springer},
year = {1994}
}
@inproceedings{DBLP:conf/wg/KloksKM94,
author = {Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller},
title = {Dominoes},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {903},
pages = {106--120},
publisher = {Springer},
year = {1994}
}
@inproceedings{DBLP:conf/wg/BodlaenderDJKKMT94,
author = {Hans L. Bodlaender and
Jitender S. Deogun and
Klaus Jansen and
Ton Kloks and
Dieter Kratsch and
Haiko M{\"{u}}ller and
Zsolt Tuza},
title = {Ranking of Graphs},
booktitle = {{WG}},
series = {Lecture Notes in Computer Science},
volume = {903},
pages = {292--304},
publisher = {Springer},
year = {1994}
}
@article{DBLP:journals/siamdm/KratschS93,
author = {Dieter Kratsch and
Lorna Stewart},
title = {Domination on Cocomparability Graphs},
journal = {{SIAM} J. Discret. Math.},
volume = {6},
number = {3},
pages = {400--417},
year = {1993}
}
@inproceedings{DBLP:conf/esa/KloksBMK93,
author = {Ton Kloks and
Hans L. Bodlaender and
Haiko M{\"{u}}ller and
Dieter Kratsch},
title = {Computing Treewidth and Minimum Fill-In: All You Need are the Minimal
Separators},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {726},
pages = {260--271},
publisher = {Springer},
year = {1993}
}
@inproceedings{DBLP:conf/icalp/BodlaenderKK93,
author = {Hans L. Bodlaender and
Ton Kloks and
Dieter Kratsch},
title = {Treewidth and Pathwidth of Permutation Graphs},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {700},
pages = {114--125},
publisher = {Springer},
year = {1993}
}
@inproceedings{DBLP:conf/stacs/KloksK93,
author = {Ton Kloks and
Dieter Kratsch},
title = {Treewidth of Bipartite Graphs},
booktitle = {{STACS}},
series = {Lecture Notes in Computer Science},
volume = {665},
pages = {80--89},
publisher = {Springer},
year = {1993}
}
@article{DBLP:journals/tcs/BodlaenderK92,
author = {Hans L. Bodlaender and
Dieter Kratsch},
title = {The Complexity of Coloring Games on Perfect Graphs},
journal = {Theor. Comput. Sci.},
volume = {106},
number = {2},
pages = {309--326},
year = {1992}
}
@article{DBLP:journals/jgt/ErdosGK91,
author = {Paul Erd{\"{o}}s and
John G. Gimbel and
Dieter Kratsch},
title = {Some extremal results in cochromatic and dichromatic theory},
journal = {J. Graph Theory},
volume = {15},
number = {6},
pages = {579--585},
year = {1991}
}
@inproceedings{DBLP:conf/fct/KratschH91,
author = {Dieter Kratsch and
Lane A. Hemachandra},
title = {On the Complexity of Graph Reconstruction},
booktitle = {{FCT}},
series = {Lecture Notes in Computer Science},
volume = {529},
pages = {318--328},
publisher = {Springer},
year = {1991}
}
@article{DBLP:journals/dm/Kratsch90,
author = {Dieter Kratsch},
title = {Finding dominating cliques efficiently, in strongly chordal graphs
and undirected path graphs},
journal = {Discret. Math.},
volume = {86},
number = {1-3},
pages = {225--238},
year = {1990}
}
@article{DBLP:journals/ipl/DamaschkeMK90,
author = {Peter Damaschke and
Haiko M{\"{u}}ller and
Dieter Kratsch},
title = {Domination in Convex and Chordal Bipartite Graphs},
journal = {Inf. Process. Lett.},
volume = {36},
number = {5},
pages = {231--236},
year = {1990}
}
@article{DBLP:journals/iandc/Kratsch87,
author = {Dieter Kratsch},
title = {Finding the Minimum Bandwidth of an Interval Graphs},
journal = {Inf. Comput.},
volume = {74},
number = {2},
pages = {140--158},
year = {1987}
}
@article{DBLP:journals/tcs/BrandstadtK87,
author = {Andreas Brandst{\"{a}}dt and
Dieter Kratsch},
title = {On Domination Problems for Permutation and Other Graphs},
journal = {Theor. Comput. Sci.},
volume = {54},
pages = {181--198},
year = {1987}
}
@article{DBLP:journals/eik/BrandstadtK86,
author = {Andreas Brandst{\"{a}}dt and
Dieter Kratsch},
title = {On Partitions of Permutations into Increasing and Decreasing Subsequences},
journal = {J. Inf. Process. Cybern.},
volume = {22},
number = {5/6},
pages = {263--273},
year = {1986}
}
@inproceedings{DBLP:conf/fct/BrandstadtK85,
author = {Andreas Brandst{\"{a}}dt and
Dieter Kratsch},
title = {On the restriction of some NP-complete graph problems to permutation
graphs},
booktitle = {{FCT}},
series = {Lecture Notes in Computer Science},
volume = {199},
pages = {53--62},
publisher = {Springer},
year = {1985}
}
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-10-28 22:44 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: