×
Compute Distance To:
Author ID: golovach.petr-a Recent zbMATH articles by "Golovach, Petr A."
Published as: Golovach, Petr A.; Golovach, P. A.; Golovach, Petr; Golovach, P.
Homepage: https://folk.uib.no/pgo041/
External Links: Math-Net.Ru · dblp · IdRef · theses.fr
all top 5

Co-Authors

23 single-authored
85 Fomin, Fedor V.
75 Paulusma, Daniël
44 Kratsch, Dieter
34 Heggernes, Pinar
26 Thilikos, Dimitrios M.
22 Saurabh, Saket
19 Lokshtanov, Daniel
16 Kratochvíl, Jan
15 van ’t Hof, Pim
13 Song, Jian
12 Broersma, Hajo J.
12 Kamiński, Marcin Marek
11 Fiala, Jiří
9 Van Leeuwen, Erik Jan
8 Couturier, Jean-Francois
8 Stewart, Anthony
8 Villanger, Yngve
7 Liedloff, Mathieu
7 Panolan, Fahad
7 Petrov, Nikolai Nikolaevich
6 Belmonte, Rémy
6 Dabrowski, Konrad Kazimierz
6 Lima, Paloma T.
5 Pilipczuk, Michał
5 Sayadi, Mohamed Yosri
5 Zehavi, Meirav
4 Dragan, Feodor F.
4 Kanté, Mamadou Moustapha
4 Karpov, Nikolay
4 Kulikov, Alexander S.
4 Lidický, Bernard
4 Martin, Barnaby D.
3 Cochefert, Manfred
3 Johnson, Matthew
3 Ramanujan, M. S.
3 Saei, Reza
2 Basavaraju, Manu
2 Biró, Peter
2 Bliznets, Ivan A.
2 Bomhoff, Matthijs
2 Chaplick, Steven
2 Chitnis, Rajesh Hemant
2 Fernandes dos Santos, Vinícius
2 Gaspers, Serge
2 Kaiser, Tomáš
2 Kern, Walter
2 Knop, Dušan
2 Konstantinidis, Athanasios L.
2 Lindzey, Nathan
2 Maniatis, Spyridon
2 Manne, Fredrik
2 McConnell, Ross M.
2 Meister, Daniel
2 Mertzios, George B.
2 Mihalák, Matúš
2 Montealegre, Pedro
2 Nederlof, Jesper
2 Papadopoulos, Charis
2 Patel, Viresh
2 Paul, Christophe
2 Proskurowski, Andrzej
2 Rafiey, Arash
2 Raymond, Jean-Florent
2 Ries, Bernard
2 Sæther, Sigve Hortemo
2 Spinrad, Jeremy P.
2 Stewart, Iain A.
2 Strømme, Torstein J. F.
2 Suchan, Karol
2 Suchý, Ondřej
2 Vicari, Elias
2 Widmayer, Peter
2 Woeginger, Gerhard Johannes
2 Zeman, Peter
1 Abramovskaya, Tat’yana Viktorovna
1 Bodlaender, Hans L.
1 Bonato, Anthony
1 Crespelle, Christophe
1 Hahn, Gena
1 Hall, Alex
1 Hall, Alexander
1 Komusiewicz, Christian
1 Korhonen, Janne H.
1 Lê Văn Băng
1 Mihai, Rodica
1 Misra, Pranabendu
1 Nisse, Nicolas
1 Otachi, Yota
1 Prałat, Paweł
1 Purohit, Nidhi
1 Pyatkin, Artem V.
1 Requilé, Clément
1 Simonov, Kirill
1 Stamoulis, Giannos
1 Szeider, Stefan
1 Szwarcfiter, Jayme Luiz
1 Vatshelle, Martin

Publications by Year

Citations contained in zbMATH Open

192 Publications have been cited 1,091 times in 685 Documents Cited by Year
A survey on the computational complexity of coloring graphs with forbidden subgraphs. Zbl 1359.05039
Golovach, Petr A.; Johnson, Matthew; Paulusma, Daniël; Song, Jian
50
2017
Complexity of the packing coloring problem for trees. Zbl 1219.05185
Fiala, Jiří; Golovach, Petr A.
38
2010
The capture time of a graph. Zbl 1177.91056
Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J.
31
2009
Updating the complexity status of coloring graphs without a fixed induced linear forest. Zbl 1234.68129
Broersma, Hajo; Golovach, Petr A.; Paulusma, Daniël; Song, Jian
30
2012
Pursuing a fast robber on a graph. Zbl 1192.91027
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Nisse, Nicolas; Suchan, Karol
30
2010
Intractability of clique-width parameterizations. Zbl 1207.68161
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
27
2010
Parameterized complexity of coloring problems: treewidth versus vertex cover. Zbl 1216.68127
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
21
2011
Algorithmic lower bounds for problems parameterized by clique-width. Zbl 1288.05269
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
21
2010
Contraction obstructions for treewidth. Zbl 1223.05022
Fomin, Fedor V.; Golovach, Petr; Thilikos, Dimitrios M.
21
2011
Backbone colorings for graphs: tree and path backbones. Zbl 1118.05031
Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Woeginger, Gerhard J.
19
2007
Distance constrained labelings of graphs of bounded treewidth. Zbl 1082.68080
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
18
2005
4-coloring \(H\)-free graphs when \(H\) is small. Zbl 1259.05061
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
18
2013
Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time. Zbl 1241.05030
Broersma, Hajo; Golovach, Petr A.; Paulusma, Daniël; Song, Jian
17
2012
Closing complexity gaps for coloring problems on \(H\)-free graphs. Zbl 1295.05105
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
16
2014
Paths of bounded length and their cuts: parameterized complexity and algorithms. Zbl 1248.90071
Golovach, Petr A.; Thilikos, Dimitrios M.
16
2011
Colouring of graphs with Ramsey-type forbidden subgraphs. Zbl 1279.68104
Dabrowski, Konrad K.; Golovach, Petr A.; Paulusma, Daniel
15
2014
Three complexity results on coloring \(P_k\)-free graphs. Zbl 1257.05037
Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Paulusma, Daniël
15
2013
Graph searching and interval completion. Zbl 0972.05047
Fomin, Fedor V.; Golovach, Petr A.
15
2000
Coloring graphs without short cycles and long induced paths. Zbl 1284.05098
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
13
2014
Almost optimal lower bounds for problems parameterized by clique-width. Zbl 1306.05181
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
12
2014
Solutions for the stable roommates problem with payments. Zbl 1341.05106
Biró, Péter; Bomhoff, Matthijs; Golovach, Petr A.; Kern, Walter; Paulusma, Daniël
12
2012
Obtaining planarity by contracting few edges. Zbl 1260.68156
Golovach, Petr A.; Van ’t Hof, Pim; Paulusma, Daniël
11
2013
Subset feedback vertex sets in chordal graphs. Zbl 1298.05302
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
11
2014
Contraction bidimensionality: the accurate picture. Zbl 1256.05202
Fomin, Fedor V.; Golovach, Petr; Thilikos, Dimitrios M.
11
2009
Three complexity results on coloring \(P _{k }\)-free graphs. Zbl 1267.05113
Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Paulusma, Daniël
11
2009
Parameterized complexity for domination problems on degenerate graphs. Zbl 1202.68278
Golovach, Petr A.; Villanger, Yngve
11
2008
Computational complexity of the distance constrained labeling problem for trees (extended abstract). Zbl 1153.68390
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
11
2008
List coloring in the absence of two subgraphs. Zbl 1283.05096
Golovach, Petr A.; Paulusma, Daniël
10
2014
Solutions for the stable roommates problem with payments. Zbl 1422.91546
Biró, Péter; Bomhoff, Matthijs; Golovach, Petr A.; Kern, Walter; Paulusma, Daniël
10
2014
Detecting fixed patterns in chordal graphs in polynomial time. Zbl 1291.68173
Belmonte, Rémy; Golovach, Petr A.; Heggernes, Pinar; van’t Hof, Pim; Kamiński, Marcin; Paulusma, Daniël
10
2014
Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs. Zbl 1316.05080
Broersma, Hajo; Fiala, Jiří; Golovach, Petr A.; Kaiser, Tomáš; Paulusma, Daniël; Proskurowski, Andrzej
9
2015
Enumerating minimal dominating sets in chordal bipartite graphs. Zbl 1326.05105
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve
9
2016
Parameterized algorithms for finding square roots. Zbl 1332.05136
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
9
2016
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1330.05118
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
9
2015
Parameterized algorithms to preserve connectivity. Zbl 1412.68078
Basavaraju, Manu; Fomin, Fedor V.; Golovach, Petr; Misra, Pranabendu; Ramanujan, M. S.; Saurabh, Saket
9
2014
Induced disjoint paths in AT-free graphs. Zbl 1357.68084
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
9
2012
Metric dimension of bounded tree-length graphs. Zbl 1371.68103
Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S.
8
2017
Editing to a graph of given degrees. Zbl 1322.68142
Golovach, Petr A.
8
2015
Parameterized complexity of three edge contraction problems with degree constraints. Zbl 1360.68489
Belmonte, Rémy; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël
8
2014
Coloring graphs characterized by a forbidden subgraph. Zbl 1303.05061
Golovach, Petr A.; Paulusma, Daniël; Ries, Bernard
8
2015
Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Zbl 1383.05162
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve H.; Villanger, Yngve
8
2018
Backbone colorings for networks. Zbl 1255.05076
Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Woeginger, Gerhard J.
8
2003
Finding clubs in graph classes. Zbl 1298.05092
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash
7
2014
Enumerating minimal connected dominating sets in graphs of bounded chordality. Zbl 1339.05190
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
7
2016
Editing to a connected graph of given degrees. Zbl 1426.68122
Golovach, Petr A.
7
2014
List coloring in the absence of a linear forest. Zbl 1307.05068
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
7
2015
Parameterized complexity of generalized domination problems. Zbl 1241.05108
Golovach, Petr A.; Kratochvíl, Jan; Suchý, Ondřej
7
2012
On the parameterized complexity of cutting a few vertices from a graph. Zbl 1398.68231
Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Janne H.
7
2013
Finding contractions and induced minors in chordal graphs via disjoint paths. Zbl 1350.68129
Belmonte, Rémy; Golovach, Petr A.; Heggernes, Pinar; van ’t Hof, Pim; Kamiński, Marcin; Paulusma, Daniël
7
2011
List coloring in the absence of a linear forest. Zbl 1305.05073
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
7
2011
Spanners of bounded degree graphs. Zbl 1260.68154
Fomin, Fedor V.; Golovach, Petr A.; van Leeuwen, Erik Jan
6
2011
Metric dimension of bounded width graphs. Zbl 1466.68054
Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S.
6
2015
Spanners in sparse graphs. Zbl 1234.68149
Dragan, Feodor F.; Fomin, Fedor V.; Golovach, Petr A.
6
2011
Parameterized algorithm for eternal vertex cover. Zbl 1234.68150
Fomin, Fedor V.; Gaspers, Serge; Golovach, Petr A.; Kratsch, Dieter; Saurabh, Saket
6
2010
Parameterized complexity of coloring problems: treewidth versus vertex cover (extended abstract). Zbl 1241.68071
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
6
2009
Sparse square roots. Zbl 1331.05204
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
6
2013
Increasing the minimum degree of a graph by contractions. Zbl 1296.05185
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
6
2013
Choosability of \(P _{5}\)-free graphs. Zbl 1250.68127
Golovach, Petr A.; Heggernes, Pinar
6
2009
Induced packing of odd cycles in a planar graph. Zbl 1272.05157
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
6
2009
Spanners in sparse graphs. Zbl 1153.68406
Dragan, Feodor F.; Fomin, Fedor V.; Golovach, Petr A.
6
2008
Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Zbl 1297.05163
Broersma, Hajo; Golovach, Petr A.; Patel, Viresh
5
2013
Search problems on 1-skeletons of regular polyhedrons. Zbl 0904.90091
Fomin, F. V.; Golovach, P. A.; Petrov, N. N.
5
1997
Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth. Zbl 1403.68164
Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
5
2018
Minimal dominating sets in interval graphs and trees. Zbl 1350.05121
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Villanger, Yngve
5
2017
On recognition of threshold tolerance graphs and their complements. Zbl 1350.05054
Golovach, Petr A.; Heggernes, Pinar; Lindzey, Nathan; McConnell, Ross M.; dos Santos, Vinícius Fernandes; Spinrad, Jeremy P.; Szwarcfiter, Jayme Luiz
5
2017
Some generalizations of the problem on the search number of a graph. Zbl 0883.90149
Golovach, P. A.; Petrov, N. N.
5
1995
Extremal search problem on graphs. Zbl 0713.90038
Golovach, P. A.
5
1990
Computing vertex-surjective homomorphisms to partially reflexive trees. Zbl 1251.05031
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
5
2012
Computational complexity of generalized domination: A complete dichotomy for chordal graphs. Zbl 1141.68530
Golovach, Petr; Kratochvíl, Jan
5
2007
Induced disjoint paths in circular-arc graphs in linear time. Zbl 1345.05051
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
4
2016
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 1373.05008
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
4
2018
Parameterized complexity of secluded connectivity problems. Zbl 1378.68075
Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.
4
2017
A linear kernel for finding square roots of almost planar graphs. Zbl 1378.68077
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Containment relations in split graphs. Zbl 1237.05180
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
4
2012
4-coloring \(H\)-free graphs when \(H\) is small. Zbl 1298.05117
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
4
2012
Search number, node search number, and vertex separator of a graph. Zbl 0727.90086
Golovach, P. A.
4
1991
On an extremal search problem on graphs. Zbl 0704.90105
Golovach, P. A.
4
1990
Clique-width: on the price of generality. Zbl 1421.68125
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
4
2009
Finding cactus roots in polynomial time. Zbl 1391.68051
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Contracting a chordal graph to a split graph or a tree. Zbl 1343.68116
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël
4
2011
Search in graphs. Zbl 1118.91305
Golovach, P. A.; Petrov, N. N.; Fomin, F. V.
4
2000
Squares of low clique number. Zbl 1356.05102
Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Editing to Eulerian graphs. Zbl 1360.68503
Dabrowski, Konrad K.; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniel
4
2014
Cops and robber with constraints. Zbl 1248.05120
Fomin, Fedor V.; Golovach, Petr A.; Prałat, Paweł
4
2012
Induced disjoint paths in claw-free graphs. Zbl 1365.05279
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
4
2012
Finding vertex-surjective graph homomorphisms. Zbl 1253.68149
Golovach, Petr A.; Lidický, Bernard; Martin, Barnaby; Paulusma, Daniël
4
2012
Parameterized complexity of the spanning tree congestion problem. Zbl 1253.68163
Bodlaender, Hans L.; Fomin, Fedor V.; Golovach, Petr A.; Otachi, Yota; van Leeuwen, Erik Jan
4
2012
Detecting induced minors in AT-free graphs. Zbl 1296.05183
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
3
2013
Editing to connected \(f\)-degree graph. Zbl 1388.68229
Fomin, Fedor V.; Golovach, Petr; Panolan, Fahad; Saurabh, Saket
3
2016
Equivalence of two formalizations of a search problem on a graph. Zbl 0666.90081
Golovach, P. A.
3
1989
A linear kernel for finding square roots of almost planar graphs. Zbl 1372.05052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
3
2017
Editing to a planar graph of given degrees. Zbl 1356.68095
Dabrowski, Konrad K.; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël; Thilikos, Dimitrios M.
3
2015
How to hunt an invisible rabbit on a graph. Zbl 1327.05233
Abramovskaya, Tatjana V.; Fomin, Fedor V.; Golovach, Petr A.; Pilipczuk, Michał
3
2016
Closing complexity gaps for coloring problems on \(H\)-free graphs. Zbl 1260.68155
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
3
2012
List coloring in the absence of two subgraphs. Zbl 1382.68109
Golovach, Petr A.; Paulusma, Daniël
3
2013
Sort and Search: exact algorithms for generalized domination. Zbl 1197.05104
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
3
2009
Hadwiger number of graphs with small chordality. Zbl 1417.05209
Golovach, Petr A.; Heggernes, Pinar; van’t Hof, Pim; Paul, Christophe
3
2014
Computing vertex-surjective homomorphisms to partially reflexive trees. Zbl 1332.68073
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
3
2011
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 1476.68208
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
3
2016
Induced packing of odd cycles in planar graphs. Zbl 1232.68064
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
3
2012
Parameterized \(k\)-clustering: tractability island. Zbl 1477.68132
Fomin, Fedor V.; Golovach, Petr A.; Simonov, Kirill
1
2021
On the tractability of optimization problems on \(H\)-graphs. Zbl 1447.05142
Fomin, Fedor V.; Golovach, Petr A.; Raymond, Jean-Florent
3
2020
Approximation schemes for low-rank binary matrix approximation problems. Zbl 1454.68180
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket
2
2020
Parameterized aspects of strong subgraph closure. Zbl 1442.68168
Golovach, Petr A.; Heggernes, Pinar; Konstantinidis, Athanasios L.; Lima, Paloma T.; Papadopoulos, Charis
2
2020
Parameterized low-rank binary matrix approximation. Zbl 1458.68075
Fomin, Fedor V.; Golovach, Petr A.; Panolan, Fahad
1
2020
Enumeration of minimal connected dominating sets for chordal graphs. Zbl 1437.05104
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
1
2020
Clique-width. III: Hamiltonian cycle and the odd case of graph coloring. Zbl 1458.05245
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
3
2019
Enumeration of maximal irredundant sets for claw-free graphs. Zbl 1409.05109
Golovach, Petr A.; Kratsch, Dieter; Sayadi, Mohamed Yosri
2
2019
Surjective \(H\)-colouring: new hardness results. Zbl 1425.05055
Golovach, Petr A.; Johnson, Matthew; Martin, Barnaby; Paulusma, Daniël; Stewart, Anthony
2
2019
Enumeration and maximum number of maximal irredundant sets for chordal graphs. Zbl 1416.05267
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
2
2019
Enumeration and maximum number of minimal dominating sets for chordal graphs. Zbl 1428.05139
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
2
2019
Kernelization of graph Hamiltonicity: proper \(H\)-graphs. Zbl 1476.68197
Chaplick, Steven; Fomin, Fedor V.; Golovach, Petr A.; Knop, Dušan; Zeman, Peter
1
2019
Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Zbl 1383.05162
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve H.; Villanger, Yngve
8
2018
Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth. Zbl 1403.68164
Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
5
2018
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 1373.05008
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
4
2018
Computing square roots of graphs with low maximum degree. Zbl 1395.05083
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
3
2018
Finding cactus roots in polynomial time. Zbl 1391.68052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
2
2018
On the tractability of optimization problems on \(H\)-graphs. Zbl 07378700
Fomin, Fedor V.; Golovach, Petr A.; Raymond, Jean-Florent
2
2018
A survey on the computational complexity of coloring graphs with forbidden subgraphs. Zbl 1359.05039
Golovach, Petr A.; Johnson, Matthew; Paulusma, Daniël; Song, Jian
50
2017
Metric dimension of bounded tree-length graphs. Zbl 1371.68103
Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S.
8
2017
Minimal dominating sets in interval graphs and trees. Zbl 1350.05121
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Villanger, Yngve
5
2017
On recognition of threshold tolerance graphs and their complements. Zbl 1350.05054
Golovach, Petr A.; Heggernes, Pinar; Lindzey, Nathan; McConnell, Ross M.; dos Santos, Vinícius Fernandes; Spinrad, Jeremy P.; Szwarcfiter, Jayme Luiz
5
2017
Parameterized complexity of secluded connectivity problems. Zbl 1378.68075
Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.
4
2017
A linear kernel for finding square roots of almost planar graphs. Zbl 1372.05052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
3
2017
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Zbl 1421.68081
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Lima, Paloma T.; Paulusma, Daniël
2
2017
Graph editing to a given degree sequence. Zbl 1356.68098
Golovach, Petr A.; Mertzios, George B.
2
2017
Spanning circuits in regular matroids. Zbl 1410.68164
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
2
2017
Enumeration and maximum number of maximal irredundant sets for chordal graphs. Zbl 1483.05180
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
1
2017
Enumeration of maximal irredundant sets for claw-free graphs. Zbl 1441.05015
Golovach, Petr A.; Kratsch, Dieter; Sayadi, Mohamed Yosri
1
2017
Editing to a planar graph of given degrees. Zbl 1356.68096
Dabrowski, Konrad K.; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël; Thilikos, Dimitrios M.
1
2017
Editing to a connected graph of given degrees. Zbl 1376.68066
Golovach, Petr A.
1
2017
Covering vectors by spaces: regular matroids. Zbl 1441.68106
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
1
2017
The parameterized complexity of graph cyclability. Zbl 1358.05077
Golovach, Petr A.; Kamiński, Marcin; Maniatis, Spyridon; Thilikos, Dimitrios M.
1
2017
Enumerating minimal dominating sets in chordal bipartite graphs. Zbl 1326.05105
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve
9
2016
Parameterized algorithms for finding square roots. Zbl 1332.05136
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
9
2016
Enumerating minimal connected dominating sets in graphs of bounded chordality. Zbl 1339.05190
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
7
2016
Induced disjoint paths in circular-arc graphs in linear time. Zbl 1345.05051
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
4
2016
A linear kernel for finding square roots of almost planar graphs. Zbl 1378.68077
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Finding cactus roots in polynomial time. Zbl 1391.68051
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Squares of low clique number. Zbl 1356.05102
Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Editing to connected \(f\)-degree graph. Zbl 1388.68229
Fomin, Fedor V.; Golovach, Petr; Panolan, Fahad; Saurabh, Saket
3
2016
How to hunt an invisible rabbit on a graph. Zbl 1327.05233
Abramovskaya, Tatjana V.; Fomin, Fedor V.; Golovach, Petr A.; Pilipczuk, Michał
3
2016
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 1476.68208
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
3
2016
Editing to Eulerian graphs. Zbl 1346.05150
Dabrowski, Konrad K.; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël
2
2016
Parameterized complexity of the anchored \(k\)-core problem for directed graphs. Zbl 1336.68119
Chitnis, Rajesh; Fomin, Fedor V.; Golovach, Petr A.
2
2016
Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs. Zbl 1316.05080
Broersma, Hajo; Fiala, Jiří; Golovach, Petr A.; Kaiser, Tomáš; Paulusma, Daniël; Proskurowski, Andrzej
9
2015
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1330.05118
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
9
2015
Editing to a graph of given degrees. Zbl 1322.68142
Golovach, Petr A.
8
2015
Coloring graphs characterized by a forbidden subgraph. Zbl 1303.05061
Golovach, Petr A.; Paulusma, Daniël; Ries, Bernard
8
2015
List coloring in the absence of a linear forest. Zbl 1307.05068
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
7
2015
Metric dimension of bounded width graphs. Zbl 1466.68054
Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S.
6
2015
Editing to a planar graph of given degrees. Zbl 1356.68095
Dabrowski, Konrad K.; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël; Thilikos, Dimitrios M.
3
2015
Induced disjoint paths in claw-free graphs. Zbl 1311.05090
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
2
2015
Hadwiger number of graphs with small chordality. Zbl 1327.05322
Golovach, Petr A.; Heggernes, Pinar; van ’t Hof, Pim; Paul, Christophe
2
2015
Parameterized complexity of secluded connectivity problems. Zbl 1366.68091
Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.
1
2015
Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Zbl 1382.05033
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve H.; Villanger, Yngve
1
2015
Closing complexity gaps for coloring problems on \(H\)-free graphs. Zbl 1295.05105
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
16
2014
Colouring of graphs with Ramsey-type forbidden subgraphs. Zbl 1279.68104
Dabrowski, Konrad K.; Golovach, Petr A.; Paulusma, Daniel
15
2014
Coloring graphs without short cycles and long induced paths. Zbl 1284.05098
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
13
2014
Almost optimal lower bounds for problems parameterized by clique-width. Zbl 1306.05181
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
12
2014
Subset feedback vertex sets in chordal graphs. Zbl 1298.05302
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
11
2014
List coloring in the absence of two subgraphs. Zbl 1283.05096
Golovach, Petr A.; Paulusma, Daniël
10
2014
Solutions for the stable roommates problem with payments. Zbl 1422.91546
Biró, Péter; Bomhoff, Matthijs; Golovach, Petr A.; Kern, Walter; Paulusma, Daniël
10
2014
Detecting fixed patterns in chordal graphs in polynomial time. Zbl 1291.68173
Belmonte, Rémy; Golovach, Petr A.; Heggernes, Pinar; van’t Hof, Pim; Kamiński, Marcin; Paulusma, Daniël
10
2014
Parameterized algorithms to preserve connectivity. Zbl 1412.68078
Basavaraju, Manu; Fomin, Fedor V.; Golovach, Petr; Misra, Pranabendu; Ramanujan, M. S.; Saurabh, Saket
9
2014
Parameterized complexity of three edge contraction problems with degree constraints. Zbl 1360.68489
Belmonte, Rémy; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël
8
2014
Finding clubs in graph classes. Zbl 1298.05092
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash
7
2014
Editing to a connected graph of given degrees. Zbl 1426.68122
Golovach, Petr A.
7
2014
Editing to Eulerian graphs. Zbl 1360.68503
Dabrowski, Konrad K.; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniel
4
2014
Hadwiger number of graphs with small chordality. Zbl 1417.05209
Golovach, Petr A.; Heggernes, Pinar; van’t Hof, Pim; Paul, Christophe
3
2014
Parameterized complexity of connected even/odd subgraph problems. Zbl 1311.68075
Fomin, Fedor V.; Golovach, Petr A.
2
2014
Induced disjoint paths in circular-arc graphs in linear time. Zbl 1417.05109
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
2
2014
Editing to a graph of given degrees. Zbl 1380.68222
Golovach, Petr A.
1
2014
Long circuits and large Euler subgraphs. Zbl 1298.05300
Fomin, Fedor V.; Golovach, Petr A.
1
2014
4-coloring \(H\)-free graphs when \(H\) is small. Zbl 1259.05061
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
18
2013
Three complexity results on coloring \(P_k\)-free graphs. Zbl 1257.05037
Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Paulusma, Daniël
15
2013
Obtaining planarity by contracting few edges. Zbl 1260.68156
Golovach, Petr A.; Van ’t Hof, Pim; Paulusma, Daniël
11
2013
On the parameterized complexity of cutting a few vertices from a graph. Zbl 1398.68231
Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Janne H.
7
2013
Sparse square roots. Zbl 1331.05204
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
6
2013
Increasing the minimum degree of a graph by contractions. Zbl 1296.05185
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
6
2013
Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Zbl 1297.05163
Broersma, Hajo; Golovach, Petr A.; Patel, Viresh
5
2013
Detecting induced minors in AT-free graphs. Zbl 1296.05183
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
3
2013
List coloring in the absence of two subgraphs. Zbl 1382.68109
Golovach, Petr A.; Paulusma, Daniël
3
2013
Parameterized complexity of two edge contraction problems with degree constraints. Zbl 1360.68488
Belmonte, Rémy; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël
3
2013
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1336.05133
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
2
2013
Long circuits and large Euler subgraphs. Zbl 1395.68149
Fomin, Fedor V.; Golovach, Petr A.
2
2013
Colouring of graphs with Ramsey-type forbidden subgraphs. Zbl 1417.68064
Dabrowski, Konrad K.; Golovach, Petr A.; Paulusma, Daniël
2
2013
Parameterized complexity of the anchored \(k\)-core problem for directed graphs. Zbl 1359.68124
Chitnis, Rajesh; Fomin, Fedor V.; Golovach, Petr A.
2
2013
Choosability on \(H\)-free graphs. Zbl 1259.68092
Golovach, Petr A.; Heggernes, Pinar; van ’t Hof, Pim; Paulusma, Daniël
1
2013
Colorings with few colors: counting, enumeration and combinatorial bounds. Zbl 1269.05034
Couturier, Jean-Francois; Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Pyatkin, Artem
1
2013
Updating the complexity status of coloring graphs without a fixed induced linear forest. Zbl 1234.68129
Broersma, Hajo; Golovach, Petr A.; Paulusma, Daniël; Song, Jian
30
2012
Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time. Zbl 1241.05030
Broersma, Hajo; Golovach, Petr A.; Paulusma, Daniël; Song, Jian
17
2012
Solutions for the stable roommates problem with payments. Zbl 1341.05106
Biró, Péter; Bomhoff, Matthijs; Golovach, Petr A.; Kern, Walter; Paulusma, Daniël
12
2012
Induced disjoint paths in AT-free graphs. Zbl 1357.68084
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
9
2012
Parameterized complexity of generalized domination problems. Zbl 1241.05108
Golovach, Petr A.; Kratochvíl, Jan; Suchý, Ondřej
7
2012
Computing vertex-surjective homomorphisms to partially reflexive trees. Zbl 1251.05031
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
5
2012
Containment relations in split graphs. Zbl 1237.05180
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
4
2012
4-coloring \(H\)-free graphs when \(H\) is small. Zbl 1298.05117
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
4
2012
Cops and robber with constraints. Zbl 1248.05120
Fomin, Fedor V.; Golovach, Petr A.; Prałat, Paweł
4
2012
Induced disjoint paths in claw-free graphs. Zbl 1365.05279
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
4
2012
...and 92 more Documents
all top 5

Cited by 909 Authors

80 Paulusma, Daniël
79 Golovach, Petr A.
36 Fomin, Fedor V.
29 Kratsch, Dieter
27 Thilikos, Dimitrios M.
25 Saurabh, Saket
19 Dabrowski, Konrad Kazimierz
18 Heggernes, Pinar
17 Lokshtanov, Daniel
15 Malyshev, Dmitry S.
14 Kratochvíl, Jan
12 Chudnovsky, Maria
12 Johnson, Matthew
12 Kamiński, Marcin Marek
11 Niedermeier, Rolf
11 Van Leeuwen, Erik Jan
10 Brešar, Boštjan
10 Kanté, Mamadou Moustapha
10 Liedloff, Mathieu
9 Fiala, Jiří
9 Martin, Barnaby D.
9 Nisse, Nicolas
9 Ono, Hirotaka
9 Ries, Bernard
9 Schaudt, Oliver
9 Song, Jian
9 Telle, Jan Arne
9 Zhong, Mingxian
8 Bonato, Anthony
8 Broersma, Hajo J.
8 Hanaka, Tesshu
8 Huang, Shenwei
8 Klavžar, Sandi
8 Kwon, Ojoung
8 Lozin, Vadim Vladislavovich
8 Otachi, Yota
8 van ’t Hof, Pim
7 Couturier, Jean-Francois
7 Gavenčiak, Tomáš
7 Gutin, Gregory Z.
7 Havet, Frédéric
7 Knop, Dušan
7 Lima, Paloma T.
7 Nichterlein, André
7 Panolan, Fahad
7 Papadopoulos, Charis
7 Pilipczuk, Michał
7 Sau, Ignasi
7 Tale, Prafullkumar
6 Bu, Yuehua
6 Dragan, Feodor F.
6 Fluschnik, Till
6 Gurski, Frank
6 Jansen, Bart M. P.
6 Lidický, Bernard
6 Mertzios, George B.
6 Rossmanith, Peter
6 Rzążewski, Paweł
6 Stewart, Anthony
6 Togni, Olivier
6 Uno, Yushi
6 Wahlström, Magnus
5 Asahiro, Yuichi
5 Belmonte, Rémy
5 Bergougnoux, Benjamin
5 Dereniowski, Dariusz
5 Ganian, Robert
5 Gaspers, Serge
5 Gastineau, Nicolas
5 Hell, Pavol
5 Mehrabian, Abbas
5 Milanič, Martin
5 Miyano, Eiji
5 Molter, Hendrik
5 Pérennes, Stéphane
5 Prałat, Paweł
5 Rall, Douglas F.
5 Ramanujan, M. S.
5 Sayadi, Mohamed Yosri
5 Spirkl, Sophie Theresa
5 Suchý, Ondřej
5 Uno, Takeaki
5 Villanger, Yngve
5 Yang, Boting
4 Adler, Isolde
4 Bodlaender, Hans L.
4 Bonomo-Braberman, Flavia
4 Brettell, Nick
4 Dondi, Riccardo
4 Ekim, Tınaz
4 Eto, Hiroshi
4 Feghali, Carl
4 Fellows, Michael Ralph
4 Ferme, Jasmina
4 Goedgebeur, Jan
4 Hartung, Sepp
4 Holub, Přemysl
4 Ishii, Toshimasa
4 Jaffke, Lars
4 Janczewski, Robert
...and 809 more Authors
all top 5

Cited in 76 Serials

107 Discrete Applied Mathematics
107 Theoretical Computer Science
64 Algorithmica
28 SIAM Journal on Discrete Mathematics
26 Discrete Mathematics
26 Journal of Computer and System Sciences
22 Information Processing Letters
16 Theory of Computing Systems
11 Journal of Combinatorial Optimization
10 European Journal of Combinatorics
10 Graphs and Combinatorics
10 Information and Computation
8 Discussiones Mathematicae. Graph Theory
7 Journal of Combinatorial Theory. Series B
7 The Electronic Journal of Combinatorics
7 Journal of Discrete Algorithms
7 Discrete Optimization
6 Journal of Graph Theory
6 Optimization Letters
4 Applied Mathematics and Computation
4 SIAM Journal on Computing
4 Games and Economic Behavior
4 Aequationes Mathematicae
3 International Journal of Game Theory
3 Mathematical Programming. Series A. Series B
3 Vestnik St. Petersburg University. Mathematics
3 Journal of Graph Algorithms and Applications
2 Acta Informatica
2 Journal of Economic Theory
2 Networks
2 Acta Mathematicae Applicatae Sinica. English Series
2 Computational Geometry
2 European Journal of Operational Research
2 The Australasian Journal of Combinatorics
2 AKCE International Journal of Graphs and Combinatorics
2 Discrete Mathematics, Algorithms and Applications
2 Games
2 Computer Science Review
1 American Mathematical Monthly
1 Artificial Intelligence
1 Algebra Universalis
1 Journal of Combinatorial Theory. Series A
1 Journal of Mathematical Economics
1 Mathematics of Operations Research
1 Operations Research
1 Moscow University Computational Mathematics and Cybernetics
1 Bulletin of the Korean Mathematical Society
1 Combinatorica
1 Computers & Operations Research
1 International Journal of Foundations of Computer Science
1 Discrete Mathematics and Applications
1 Applied Mathematical Modelling
1 Automation and Remote Control
1 Combinatorics, Probability and Computing
1 Fractals
1 Opuscula Mathematica
1 Complexity
1 Constraints
1 INFORMS Journal on Computing
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ. Seriya 1
1 Annals of Combinatorics
1 Discrete Mathematics and Theoretical Computer Science. DMTCS
1 Data Mining and Knowledge Discovery
1 RAIRO. Operations Research
1 International Game Theory Review
1 Central European Journal of Mathematics
1 South East Asian Journal of Mathematics and Mathematical Sciences
1 Logical Methods in Computer Science
1 Advances and Applications in Discrete Mathematics
1 Algorithms
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
1 Frontiers of Computer Science
1 Palestine Journal of Mathematics
1 Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki
1 Journal of Dynamics and Games
1 Bulletin of the Hellenic Mathematical Society

Citations by Year