×
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
116 Fomin, Fedor V.
79 Paulusma, Daniël
44 Kratsch, Dieter
36 Thilikos, Dimitrios M.
34 Heggernes, Pinar
32 Saurabh, Saket
22 Lokshtanov, Daniel
16 Kratochvíl, Jan
15 van ’t Hof, Pim
13 Panolan, Fahad
13 Song, Jian
12 Broersma, Hajo J.
12 Kamiński, Marcin Marek
11 Fiala, Jiří
10 Simonov, Kirill
10 Zehavi, Meirav
9 Van Leeuwen, Erik Jan
8 Couturier, Jean-Francois
8 Lima, Paloma T.
8 Martin, Barnaby D.
8 Stewart, Anthony
8 Villanger, Yngve
7 Liedloff, Mathieu
7 Petrov, Nikolai Nikolaevich
7 Stamoulis, Giannos
6 Belmonte, Rémy
6 Dabrowski, Konrad Kazimierz
5 Pilipczuk, Michał
5 Purohit, Nidhi
5 Sayadi, Mohamed Yosri
4 Bandyapadhyay, Sayan
4 Brause, Christoph
4 Dragan, Feodor F.
4 Kanté, Mamadou Moustapha
4 Karpov, Nikolay
4 Kulikov, Alexander S.
4 Lidický, Bernard
4 Lochet, William
4 Misra, Pranabendu
4 Papadopoulos, Charis
4 Ramanujan, M. S.
4 Smith, Siani
3 Chaplick, Steven
3 Cochefert, Manfred
3 Crespelle, Christophe
3 Johnson, Matthew
3 Knop, Dušan
3 Saei, Reza
3 Sagunov, Danil
2 Basavaraju, Manu
2 Biró, Peter
2 Bliznets, Ivan A.
2 Bomhoff, Matthijs
2 Chitnis, Rajesh Hemant
2 dos Santos, Vinícius Fernandes
2 Gaspers, Serge
2 Inamdar, Tanmay C.
2 Kaiser, Tomáš
2 Kern, Walter
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 Patel, Viresh
2 Paul, Christophe
2 Philip, Geevarghese
2 Proskurowski, Andrzej
2 Rafiey, Arash
2 Raymond, Jean-Florent
2 Ries, Bernard
2 Sæther, Sigve Hortemo
2 Sharma, Roohani
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
2 Zeman, Peter
1 Abramovskaya, Tat’yana Viktorovna
1 Bodlaender, Hans L.
1 Bonato, Anthony
1 Dallard, Clément
1 Drange, Pål Grønås
1 Eiben, Eduard
1 Feghali, Carl
1 Fellows, Michael Ralph
1 Fraigniaud, Pierre
1 Hahn, Gena
1 Hall, Alex
1 Hall, Alexander
1 Hartmann, Tim A.
...and 26 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

232 Publications have been cited 1,600 times in 969 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
77
2017
Complexity of the packing coloring problem for trees. Zbl 1219.05185
Fiala, Jiří; Golovach, Petr A.
42
2010
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
40
2012
Intractability of clique-width parameterizations. Zbl 1207.68161
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
38
2010
Parameterized complexity of coloring problems: treewidth versus vertex cover. Zbl 1216.68127
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
36
2011
Pursuing a fast robber on a graph. Zbl 1192.91027
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Nisse, Nicolas; Suchan, Karol
36
2010
The capture time of a graph. Zbl 1177.91056
Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J.
34
2009
Algorithmic lower bounds for problems parameterized by clique-width. Zbl 1288.05269
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
28
2010
Contraction obstructions for treewidth. Zbl 1223.05022
Fomin, Fedor V.; Golovach, Petr; Thilikos, Dimitrios M.
27
2011
Distance constrained labelings of graphs of bounded treewidth. Zbl 1082.68080
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
25
2005
Closing complexity gaps for coloring problems on \(H\)-free graphs. Zbl 1295.05105
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
25
2014
Three complexity results on coloring \(P_k\)-free graphs. Zbl 1257.05037
Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Paulusma, Daniël
24
2013
Almost optimal lower bounds for problems parameterized by clique-width. Zbl 1306.05181
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
22
2014
Obtaining planarity by contracting few edges. Zbl 1260.68156
Golovach, Petr A.; Van ’t Hof, Pim; Paulusma, Daniël
22
2013
4-coloring \(H\)-free graphs when \(H\) is small. Zbl 1259.05061
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
21
2013
Paths of bounded length and their cuts: parameterized complexity and algorithms. Zbl 1248.90071
Golovach, Petr A.; Thilikos, Dimitrios M.
21
2011
Coloring graphs without short cycles and long induced paths. Zbl 1284.05098
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
21
2014
Backbone colorings for graphs: tree and path backbones. Zbl 1118.05031
Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Woeginger, Gerhard J.
20
2007
Colouring of graphs with Ramsey-type forbidden subgraphs. Zbl 1279.68104
Dabrowski, Konrad K.; Golovach, Petr A.; Paulusma, Daniel
20
2014
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
19
2012
Parameterized complexity for domination problems on degenerate graphs. Zbl 1202.68278
Golovach, Petr A.; Villanger, Yngve
19
2008
Clique-width: on the price of generality. Zbl 1421.68125
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
19
2009
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
18
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
17
2015
Parameterized algorithms to preserve connectivity. Zbl 1412.68078
Basavaraju, Manu; Fomin, Fedor V.; Golovach, Petr; Misra, Pranabendu; Ramanujan, M. S.; Saurabh, Saket
16
2014
Metric dimension of bounded tree-length graphs. Zbl 1371.68103
Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S.
16
2017
Subset feedback vertex sets in chordal graphs. Zbl 1298.05302
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
16
2014
Graph searching and interval completion. Zbl 0972.05047
Fomin, Fedor V.; Golovach, Petr A.
15
2000
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
15
2014
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1330.05118
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
15
2015
On the tractability of optimization problems on \(H\)-graphs. Zbl 1447.05142
Fomin, Fedor V.; Golovach, Petr A.; Raymond, Jean-Florent
15
2020
Contraction bidimensionality: the accurate picture. Zbl 1256.05202
Fomin, Fedor V.; Golovach, Petr; Thilikos, Dimitrios M.
14
2009
Computational complexity of the distance constrained labeling problem for trees (extended abstract). Zbl 1153.68390
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
14
2008
Enumerating minimal dominating sets in chordal bipartite graphs. Zbl 1326.05105
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve
13
2016
On the parameterized complexity of cutting a few vertices from a graph. Zbl 1398.68231
Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Janne H.
13
2013
Parameterized algorithm for eternal vertex cover. Zbl 1234.68150
Fomin, Fedor V.; Gaspers, Serge; Golovach, Petr A.; Kratsch, Dieter; Saurabh, Saket
12
2010
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
List coloring in the absence of two subgraphs. Zbl 1283.05096
Golovach, Petr A.; Paulusma, Daniël
12
2014
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
Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Zbl 1383.05162
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve H.; Villanger, Yngve
11
2018
Finding clubs in graph classes. Zbl 1298.05092
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash
11
2014
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
11
2019
Solutions for the stable roommates problem with payments. Zbl 1422.91546
Biró, Péter; Bomhoff, Matthijs; Golovach, Petr A.; Kern, Walter; Paulusma, Daniël
11
2014
Induced disjoint paths in AT-free graphs. Zbl 1357.68084
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
10
2012
Coloring graphs characterized by a forbidden subgraph. Zbl 1303.05061
Golovach, Petr A.; Paulusma, Daniël; Ries, Bernard
10
2015
Parameterized algorithms for finding square roots. Zbl 1332.05136
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
10
2016
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
10
2015
Increasing the minimum degree of a graph by contractions. Zbl 1296.05185
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
10
2013
Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth. Zbl 1403.68164
Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
9
2018
Editing to a connected graph of given degrees. Zbl 1426.68122
Golovach, Petr A.
9
2014
Editing to a graph of given degrees. Zbl 1322.68142
Golovach, Petr A.
9
2015
Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Zbl 1297.05163
Broersma, Hajo; Golovach, Petr A.; Patel, Viresh
9
2013
Spanners in sparse graphs. Zbl 1234.68149
Dragan, Feodor F.; Fomin, Fedor V.; Golovach, Petr A.
8
2011
Parameterized complexity of generalized domination problems. Zbl 1241.05108
Golovach, Petr A.; Kratochvíl, Jan; Suchý, Ondřej
8
2012
Induced packing of odd cycles in a planar graph. Zbl 1272.05157
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
8
2009
Backbone colorings for networks. Zbl 1255.05076
Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Woeginger, Gerhard J.
8
2003
Metric dimension of bounded width graphs. Zbl 1466.68054
Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S.
8
2015
Enumerating minimal connected dominating sets in graphs of bounded chordality. Zbl 1339.05190
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
8
2016
Induced disjoint paths in circular-arc graphs in linear time. Zbl 1345.05051
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
8
2016
Spanners of bounded degree graphs. Zbl 1260.68154
Fomin, Fedor V.; Golovach, Petr A.; van Leeuwen, Erik Jan
8
2011
Computing vertex-surjective homomorphisms to partially reflexive trees. Zbl 1251.05031
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
7
2012
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
Parameterized complexity of coloring problems: treewidth versus vertex cover (extended abstract). Zbl 1241.68071
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
7
2009
Some generalizations of the problem on the search number of a graph. Zbl 0883.90149
Golovach, P. A.; Petrov, N. N.
7
1995
Parameterized complexity of secluded connectivity problems. Zbl 1378.68075
Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.
7
2017
Induced disjoint paths in claw-free graphs. Zbl 1311.05090
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
7
2015
Spanners in sparse graphs. Zbl 1153.68406
Dragan, Feodor F.; Fomin, Fedor V.; Golovach, Petr A.
7
2008
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
7
2012
Sparse square roots. Zbl 1331.05204
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
7
2013
On the tractability of optimization problems on \(H\)-graphs. Zbl 1524.68228
Fomin, Fedor V.; Golovach, Petr A.; Raymond, Jean-Florent
7
2018
Search in graphs. Zbl 1118.91305
Golovach, P. A.; Petrov, N. N.; Fomin, F. V.
6
2000
Computational complexity of generalized domination: A complete dichotomy for chordal graphs. Zbl 1141.68530
Golovach, Petr; Kratochvíl, Jan
6
2007
Cops and robber with constraints. Zbl 1248.05120
Fomin, Fedor V.; Golovach, Petr A.; Prałat, Paweł
6
2012
Distance three labelings of trees. Zbl 1241.05123
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan; Lidický, Bernard; Paulusma, Daniël
6
2012
Choosability of \(P _{5}\)-free graphs. Zbl 1250.68127
Golovach, Petr A.; Heggernes, Pinar
6
2009
Minimal dominating sets in interval graphs and trees. Zbl 1350.05121
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Villanger, Yngve
6
2017
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
6
2017
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 1373.05008
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
6
2018
The parameterized complexity of graph cyclability. Zbl 1358.05077
Golovach, Petr A.; Kamiński, Marcin; Maniatis, Spyridon; Thilikos, Dimitrios M.
6
2017
Search problems on 1-skeletons of regular polyhedrons. Zbl 0904.90091
Fomin, F. V.; Golovach, P. A.; Petrov, N. N.
5
1997
How to guard a graph? Zbl 1233.91047
Fomin, Fedor V.; Golovach, Petr A.; Hall, Alex; Mihalák, Matúš; Vicari, Elias; Widmayer, Peter
5
2011
How to guard a graph? Zbl 1183.91021
Fomin, Fedor V.; Golovach, Petr A.; Hall, Alexander; Mihalák, Matúš; Vicari, Elias; Widmayer, Peter
5
2008
Extremal search problem on graphs. Zbl 0713.90038
Golovach, P. A.
5
1990
How to hunt an invisible rabbit on a graph. Zbl 1327.05233
Abramovskaya, Tatjana V.; Fomin, Fedor V.; Golovach, Petr A.; Pilipczuk, Michał
5
2016
Editing to Eulerian graphs. Zbl 1360.68503
Dabrowski, Konrad K.; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniel
5
2014
Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. Zbl 1479.68002
Golovach, Petr A.; Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang
5
2022
Induced disjoint paths in AT-free graphs. Zbl 1478.68240
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
5
2022
Parameterized low-rank binary matrix approximation. Zbl 1458.68075
Fomin, Fedor V.; Golovach, Petr A.; Panolan, Fahad
5
2020
Acyclic, star, and injective colouring: bounding the diameter. Zbl 07538588
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Paulusma, Daniël; Smith, Siani
5
2021
Subgraph complementation. Zbl 1439.05212
Fomin, Fedor V.; Golovach, Petr A.; Strømme, Torstein J. F.; Thilikos, Dimitrios M.
5
2020
Equivalence of two formalizations of a search problem on a graph. Zbl 0666.90081
Golovach, P. A.
4
1989
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
Induced disjoint paths in claw-free graphs. Zbl 1365.05279
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
4
2012
Guard games on graphs: keep the intruder out! Zbl 1227.68031
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel
4
2011
Containment relations in split graphs. Zbl 1237.05180
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M.
4
2012
Systems of pairs of \(q\)-distant representatives, and graph colorings. Zbl 1078.05031
Golovach, P. A.
4
2002
On an extremal search problem on graphs. Zbl 0704.90105
Golovach, P. A.
4
1990
Search number, node search number, and vertex separator of a graph. Zbl 0727.90086
Golovach, P. A.
4
1991
Minimal trees with given vertex-search number. Zbl 0769.05030
Golovach, P. A.
4
1992
A survey of parameterized algorithms and the complexity of edge modification. Zbl 07698754
Crespelle, Christophe; Drange, Pål Grønås; Fomin, Fedor V.; Golovach, Petr
2
2023
How to find a good explanation for clustering? Zbl 07732223
Bandyapadhyay, Sayan; Fomin, Fedor V.; Golovach, Petr A.; Lochet, William; Purohit, Nidhi; Simonov, Kirill
1
2023
Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. Zbl 1479.68002
Golovach, Petr A.; Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang
5
2022
Induced disjoint paths in AT-free graphs. Zbl 1478.68240
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
5
2022
Acyclic, star, and injective colouring: bounding the diameter. Zbl 1491.05074
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Ochem, Pascal; Paulusma, Daniël; Smith, Siani
4
2022
Parameterized complexity of elimination distance to first-order logic properties. Zbl 1505.03075
Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M.
3
2022
Lossy kernelization of same-size clustering. Zbl 07615733
Bandyapadhyay, Sayan; Fomin, Fedor V.; Golovach, Petr A.; Purohit, Nidhi; Siminov, Kirill
1
2022
Partitioning \(H\)-free graphs of bounded diameter. Zbl 07575095
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Paulusma, Daniël; Smith, Siani
1
2022
Present-biased optimization. Zbl 1497.91088
Fomin, Fedor V.; Fraigniaud, Pierre; Golovach, Petr A.
1
2022
Cyclability in graph classes. Zbl 1485.05156
Crespelle, Christophe; Golovach, Petr A.
1
2022
Acyclic, star, and injective colouring: bounding the diameter. Zbl 07538588
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Paulusma, Daniël; Smith, Siani
5
2021
16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. Zbl 1482.68023
4
2021
Kernelization of graph Hamiltonicity: proper \(H\)-graphs. Zbl 1476.68198
Chaplick, Steven; Fomin, Fedor V.; Golovach, Petr A.; Knop, Dušan; Zeman, Peter
3
2021
Subexponential parameterized algorithms and kernelization on almost chordal graphs. Zbl 1467.05254
Fomin, Fedor V.; Golovach, Petr A.
3
2021
Parameterized \(k\)-clustering: tractability island. Zbl 1477.68132
Fomin, Fedor V.; Golovach, Petr A.; Simonov, Kirill
2
2021
Multiplicative parameterization above a guarantee. Zbl 1495.68103
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav
2
2021
Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs. Zbl 07538586
Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M.
1
2021
Parameterized complexity of categorical clustering with size constraints. Zbl 07498691
Fomin, Fedor V.; Golovach, Petr A.; Purohit, Nidhi
1
2021
On the tractability of optimization problems on \(H\)-graphs. Zbl 1447.05142
Fomin, Fedor V.; Golovach, Petr A.; Raymond, Jean-Florent
15
2020
Parameterized low-rank binary matrix approximation. Zbl 1458.68075
Fomin, Fedor V.; Golovach, Petr A.; Panolan, Fahad
5
2020
Subgraph complementation. Zbl 1439.05212
Fomin, Fedor V.; Golovach, Petr A.; Strømme, Torstein J. F.; Thilikos, Dimitrios M.
5
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
4
2020
Hitting topological minor models in planar graphs is fixed parameter tractable. Zbl 07304079
Golovach, Petr A.; Stamoulis, Giannos; Thilikos, Dimitrios M.
4
2020
On the parameterized complexity of graph modification to first-order logic properties. Zbl 1434.68208
Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M.
4
2020
An algorithmic meta-theorem for graph modification to planarity and FOL. Zbl 07651190
Fomin, Fedor V.; Golovach, Petr A.; Stamoulis, Giannos; Thilikos, Dimitrios M.
3
2020
Enumeration of minimal connected dominating sets for chordal graphs. Zbl 1437.05104
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza
3
2020
Parameterized aspects of strong subgraph closure. Zbl 1442.68168
Golovach, Petr A.; Heggernes, Pinar; Konstantinidis, Athanasios L.; Lima, Paloma T.; Papadopoulos, Charis
3
2020
Going far from degeneracy. Zbl 1451.05229
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav
2
2020
Diverse pairs of matchings. Zbl 07765384
Fomin, Fedor V.; Golovach, Petr A.; Jaffke, Lars; Philip, Geevarghese; Sagunov, Danil
2
2020
Finding connected secluded subgraphs. Zbl 1443.68130
Golovach, Petr A.; Heggernes, Pinar; Lima, Paloma T.; Montealegre, Pedro
2
2020
Recognizing proper tree-graphs. Zbl 07764099
Chaplick, Steven; Golovach, Petr A.; Hartmann, Tim A.; Knop, Dušan
1
2020
Graph square roots of small distance from degree one graphs. Zbl 07600769
Golovach, Petr A.; Lima, Paloma T.; Papadopoulos, Charis
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
11
2019
Kernelization of graph Hamiltonicity: proper \(H\)-graphs. Zbl 1476.68197
Chaplick, Steven; Fomin, Fedor V.; Golovach, Petr A.; Knop, Dušan; Zeman, Peter
4
2019
Surjective \(H\)-colouring: new hardness results. Zbl 1425.05055
Golovach, Petr A.; Johnson, Matthew; Martin, Barnaby; Paulusma, Daniël; Stewart, Anthony
3
2019
Modification to planarity is fixed parameter tractable. Zbl 07559137
Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M.
3
2019
Enumeration and maximum number of minimal dominating sets for chordal graphs. Zbl 1428.05139
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
3
2019
Enumeration of maximal irredundant sets for claw-free graphs. Zbl 1409.05109
Golovach, Petr A.; Kratsch, Dieter; Sayadi, Mohamed Yosri
2
2019
Enumeration and maximum number of maximal irredundant sets for chordal graphs. Zbl 1416.05267
Golovach, Petr A.; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri
2
2019
Editing to connected \(f\)-degree graph. Zbl 1429.68189
Fomin, Fedor V.; Golovach, Petr; Panolan, Fahad; Saurabh, Saket
2
2019
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Zbl 1421.68082
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Lima, Paloma T.; Paulusma, Daniël
1
2019
Clustering to given connectivities. Zbl 07650226
Golovach, Petr A.; Thilikos, Dimitrios M.
1
2019
Parameterized \(k\)-clustering: tractability island. Zbl 07650311
Fomin, Fedor V.; Golovach, Petr A.; Simonov, Kirill
1
2019
Covering vectors by spaces in perturbed graphic matroids and their duals. Zbl 07561552
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
1
2019
Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Zbl 1383.05162
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve H.; Villanger, Yngve
11
2018
Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth. Zbl 1403.68164
Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
9
2018
On the tractability of optimization problems on \(H\)-graphs. Zbl 1524.68228
Fomin, Fedor V.; Golovach, Petr A.; Raymond, Jean-Florent
7
2018
Enumeration and maximum number of minimal connected vertex covers in graphs. Zbl 1373.05008
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
6
2018
Finding cactus roots in polynomial time. Zbl 1391.68052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2018
Finding connected secluded subgraphs. Zbl 1443.68129
Golovach, Petr A.; Heggernes, Pinar; Lima, Paloma T.; Montealegre, Pedro
4
2018
Computing square roots of graphs with low maximum degree. Zbl 1395.05083
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2018
Parameterized aspects of strong subgraph closure. Zbl 1442.68169
Golovach, Petr A.; Heggernes, Pinar; Konstantinidis, Athanasios L.; Lima, Paloma T.; Papadopoulos, Charis
3
2018
Partial complementation of graphs. Zbl 1477.68225
Fomin, Fedor V.; Golovach, Petr A.; Strømme, Torstein J. F.; Thilikos, Dimitrios M.
2
2018
Parameterized low-rank binary matrix approximation. Zbl 1499.68151
Fomin, Fedor V.; Golovach, Petr A.; Panolan, Fahad
1
2018
Covering vectors by spaces: regular matroids. Zbl 1400.05045
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
1
2018
Structured connectivity augmentation. Zbl 1400.05134
Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M.
1
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
77
2017
Metric dimension of bounded tree-length graphs. Zbl 1371.68103
Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S.
16
2017
Parameterized complexity of secluded connectivity problems. Zbl 1378.68075
Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.
7
2017
Minimal dominating sets in interval graphs and trees. Zbl 1350.05121
Golovach, Petr A.; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Villanger, Yngve
6
2017
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
6
2017
The parameterized complexity of graph cyclability. Zbl 1358.05077
Golovach, Petr A.; Kamiński, Marcin; Maniatis, Spyridon; Thilikos, Dimitrios M.
6
2017
Editing to a connected graph of given degrees. Zbl 1376.68066
Golovach, Petr A.
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
4
2017
Graph editing to a given degree sequence. Zbl 1356.68098
Golovach, Petr A.; Mertzios, George B.
3
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.
2
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
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
Covering vectors by spaces: regular matroids. Zbl 1441.68106
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
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
13
2016
Parameterized algorithms for finding square roots. Zbl 1332.05136
Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
10
2016
Enumerating minimal connected dominating sets in graphs of bounded chordality. Zbl 1339.05190
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter
8
2016
Induced disjoint paths in circular-arc graphs in linear time. Zbl 1345.05051
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
8
2016
How to hunt an invisible rabbit on a graph. Zbl 1327.05233
Abramovskaya, Tatjana V.; Fomin, Fedor V.; Golovach, Petr A.; Pilipczuk, Michał
5
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
Editing to connected \(f\)-degree graph. Zbl 1388.68229
Fomin, Fedor V.; Golovach, Petr; Panolan, Fahad; Saurabh, Saket
4
2016
Parameterized complexity of the anchored \(k\)-core problem for directed graphs. Zbl 1336.68119
Chitnis, Rajesh; Fomin, Fedor V.; Golovach, Petr A.
4
2016
Squares of low clique number. Zbl 1356.05102
Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Finding cactus roots in polynomial time. Zbl 1391.68051
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
4
2016
Editing to Eulerian graphs. Zbl 1346.05150
Dabrowski, Konrad K.; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël
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
List coloring in the absence of a linear forest. Zbl 1307.05068
Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël
17
2015
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Zbl 1330.05118
Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve
15
2015
Coloring graphs characterized by a forbidden subgraph. Zbl 1303.05061
Golovach, Petr A.; Paulusma, Daniël; Ries, Bernard
10
2015
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
10
2015
Editing to a graph of given degrees. Zbl 1322.68142
Golovach, Petr A.
9
2015
Metric dimension of bounded width graphs. Zbl 1466.68054
Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S.
8
2015
Induced disjoint paths in claw-free graphs. Zbl 1311.05090
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
7
2015
Hadwiger number of graphs with small chordality. Zbl 1327.05322
Golovach, Petr A.; Heggernes, Pinar; van ’t Hof, Pim; Paul, Christophe
4
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
Variants of plane diameter completion. Zbl 1378.68078
Golovach, Petr A.; Requilé, Clément; Thilikos, Dimitrios M.
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
Parameterized complexity of secluded connectivity problems. Zbl 1366.68091
Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.
1
2015
Closing complexity gaps for coloring problems on \(H\)-free graphs. Zbl 1295.05105
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
25
2014
Almost optimal lower bounds for problems parameterized by clique-width. Zbl 1306.05181
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket
22
2014
Coloring graphs without short cycles and long induced paths. Zbl 1284.05098
Golovach, Petr A.; Paulusma, Daniël; Song, Jian
21
2014
Colouring of graphs with Ramsey-type forbidden subgraphs. Zbl 1279.68104
Dabrowski, Konrad K.; Golovach, Petr A.; Paulusma, Daniel
20
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
18
2014
...and 132 more Documents
all top 5

Cited by 1,175 Authors

107 Golovach, Petr A.
107 Paulusma, Daniël
54 Fomin, Fedor V.
38 Thilikos, Dimitrios M.
36 Saurabh, Saket
29 Kratsch, Dieter
25 Dabrowski, Konrad Kazimierz
22 Lokshtanov, Daniel
22 Martin, Barnaby D.
21 Heggernes, Pinar
19 Malyshev, Dmitriĭ Sergeevich
18 Van Leeuwen, Erik Jan
16 Kratochvíl, Jan
16 Smith, Siani
15 Chudnovsky, Maria
15 Tale, Prafullkumar
15 Telle, Jan Arne
14 Lima, Paloma T.
14 Panolan, Fahad
13 Johnson, Matthew
13 Niedermeier, Rolf
13 Otachi, Yota
13 Ries, Bernard
12 Huang, Shenwei
12 Kamiński, Marcin Marek
12 Kanté, Mamadou Moustapha
12 Komusiewicz, Christian
12 Ono, Hirotaka
12 Papadopoulos, Charis
11 Brešar, Boštjan
11 Ganian, Robert
11 Hanaka, Tesshu
11 Nisse, Nicolas
11 Zhong, Mingxian
10 Fiala, Jiří
10 Knop, Dušan
10 Liedloff, Mathieu
10 Sau, Ignasi
10 Schaudt, Oliver
10 Spirkl, Sophie Theresa
9 Fluschnik, Till
9 Jansen, Bart M. P.
9 Klavžar, Sandi
9 Kwon, Ojoung
9 Munaro, Andrea
9 Pilipczuk, Michał
9 Rzążewski, Paweł
9 Song, Jian
9 van ’t Hof, Pim
8 Bonato, Anthony
8 Brettell, Nick
8 Broersma, Hajo J.
8 Gavenčiak, Tomáš
8 Gutin, Gregory Z.
8 Jaffke, Lars
8 Lampis, Michael
8 Lozin, Vadim Vladislavovich
8 Masařík, Tomáš
8 Souza, Uéverton S.
8 Szeider, Stefan
8 Uno, Takeaki
8 Uno, Yushi
7 Belmonte, Rémy
7 Bodlaender, Hans L.
7 Couturier, Jean-Francois
7 Dragan, Feodor F.
7 Ducoffe, Guillaume
7 Havet, Frédéric
7 Koana, Tomohiro
7 Milanič, Martin
7 Nichterlein, André
7 Novotná, Jana
7 Paesani, Giacomo
7 Raman, Venkatesh
7 Rossmanith, Peter
7 Sommer, Frank
7 Wahlström, Magnus
6 Agrawal, Akanksha
6 Bergougnoux, Benjamin
6 Bu, Yuehua
6 Gargano, Luisa
6 Gurski, Frank
6 Hliněný, Petr
6 Hoàng, Chính T.
6 Klimošová, Tereza
6 Konstantinidis, Athanasios L.
6 Koutecký, Martin
6 Lidický, Bernard
6 Mc Inerney, Fionn
6 Mertzios, George B.
6 Misra, Pranabendu
6 Philip, Geevarghese
6 Rall, Douglas F.
6 Ramanujan, M. S.
6 Sanità, Laura
6 Stewart, Anthony
6 Suchý, Ondřej
6 Togni, Olivier
5 Asahiro, Yuichi
5 Bonnet, Edouard
...and 1,075 more Authors
all top 5

Cited in 95 Serials

129 Theoretical Computer Science
124 Discrete Applied Mathematics
90 Algorithmica
37 SIAM Journal on Discrete Mathematics
35 Journal of Computer and System Sciences
32 Discrete Mathematics
23 Information Processing Letters
20 Theory of Computing Systems
14 Journal of Combinatorial Optimization
13 Graphs and Combinatorics
12 Information and Computation
12 The Electronic Journal of Combinatorics
11 Journal of Combinatorial Theory. Series B
11 European Journal of Combinatorics
10 Discussiones Mathematicae. Graph Theory
8 Journal of Graph Theory
8 SIAM Journal on Computing
8 Discrete Optimization
7 Journal of Discrete Algorithms
6 Optimization Letters
5 Applied Mathematics and Computation
5 Networks
5 Mathematical Programming. Series A. Series B
5 Journal of Graph Algorithms and Applications
4 Games and Economic Behavior
4 Aequationes Mathematicae
4 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
4 Computer Science Review
3 International Journal of Game Theory
3 European Journal of Operational Research
3 Vestnik St. Petersburg University. Mathematics
3 Discrete Mathematics, Algorithms and Applications
2 Acta Informatica
2 Journal of Economic Theory
2 Acta Mathematicae Applicatae Sinica. English Series
2 Discrete & Computational Geometry
2 Computational Geometry
2 The Australasian Journal of Combinatorics
2 Constraints
2 INFORMS Journal on Computing
2 AKCE International Journal of Graphs and Combinatorics
2 ACM Transactions on Algorithms
2 Games
1 Acta Mechanica
1 American Mathematical Monthly
1 Artificial Intelligence
1 Algebra Universalis
1 Information Sciences
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 Advances in Applied Mathematics
1 Bulletin of the Korean Mathematical Society
1 Combinatorica
1 Computers & Operations Research
1 Numerical Methods for Partial Differential Equations
1 International Journal of Foundations of Computer Science
1 Discrete Mathematics and Applications
1 Applied Mathematical Modelling
1 Automation and Remote Control
1 SIAM Review
1 Combinatorics, Probability and Computing
1 Computational and Applied Mathematics
1 Fractals
1 Filomat
1 Opuscula Mathematica
1 Complexity
1 International Transactions in Operational Research
1 Journal of Scheduling
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 Journal of Discrete Mathematical Sciences & Cryptography
1 New Journal of Physics
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 ACM Transactions on Computational Logic
1 Logical Methods in Computer Science
1 Advances and Applications in Discrete Mathematics
1 Algorithms
1 RAIRO. Theoretical Informatics and Applications
1 Dynamic Games and Applications
1 Journal of Mathematical Research with Applications
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 Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva
1 Bulletin of the Hellenic Mathematical Society
1 Mathematical Foundations of Computing

Citations by Year