Petr Golovach is a research professor at the Department of Informatics, University of Bergen. His main research interests are in the areas of  Discrete Mathematics and Theoretical Computer Sciences. His research spans a broad range of topics in graph theory, algorithms on graphs and matroids, clustering algorithms, complexity, parameterized complexity, enumeration algorithms.

Petr Golovach was one of the organizers of Dagstuhl Seminar 18381 “Algorithmic enumeration: output-sensitive, input-sensitive, parameterized, approximative” in 2018. He have been a program commitee member of various international workshops and conferences (STACS 2020, IPEC 2019, WG 2019 and 2016, WEPA 2018, SWAT 2014), and he is selected to be a program commitee chair of IPEC 2021.

Teaching courses 

At Syktyvkar State University (Russia) - 1991-2007:

• Programming,
• Discrete mathematics, 
• Combinatorial algorithms,
• Graph theory,
• Matroid theory,
• Computational complexity.

At Durham University (UK) - 2009-2011:

• Advanced theory of computation,
• Formal aspects of computer science.

At University of Bergen:

 Advanced theory of computation,

• Advanced algorithms techniques (INF 334) - 2015,
• Selected topics in Algorithms and Complexity, Enumeration algorithms (INF 339) - 2018.

Supervision (at Uiniversity of Bergen)

PhD students:

Nidhi Purohit, Matrix Clustering with Size Constraints.  

Master students:

Øyving Stette Haarberg, Complexity of Edge-Editing to a Connected Graph of Bounded Degree - 2019

Andreas Steinvik, Kernelization for Balanced Graph Clustering - 2020

Petr Golovach has  more that 100 papers in peer reviewed journals (including high rated academic journals like J. Comb. Theory, Ser. B,  SIAM J. Computing, SIAM J. Discrete Math., J. of Graph Theory, Algorithmica, J. Comput. Syst. Sci.) and more than 100 papers in refereed conference proceedings (including leading Theoretical Computer Science conferences like SODA, ICALP, ESA, STACS).

2024

• Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay et al. (2024). FPT approximation and subexponential algorithms for covering few or many edges. (external link)
• Fomin, Fedor; Golovach, Petr; Jaffke, Lars et al. (2024). Diverse Pairs of Matchings. (external link)
• Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay et al. (2024). (Re)packing Equal Disks into Rectangle. (external link)
• Fomin, Fedor; Fraigniaud, Pierre; Golovach, Petr (2024). Parameterized complexity of broadcasting in graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Sagunov, Danil et al. (2024). Approximating Long Cycle Above Dirac’s Guarantee. (external link)
• Bentert, Matthias; Drange, Pål Grønås; Fomin, Fedor et al. (2024). Two-Sets Cut-Uncut on Planar Graphs. (external link)

2023

• Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre et al. (2023). Detours in directed graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2023). Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Stamoulis, Giannos et al. (2023). An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL. (external link)
• Fomin, Fedor; Golovach, Petr; Purohit, Nidhi (2023). Parameterized complexity of categorical clustering with size constraints. (external link)
• Fomin, Fedor; Golovach, Petr; Panolan, Fahad et al. (2023). Diverse collections in matroids and graphs. (external link)
• Bentert, Matthias; Drange, Pål Grønås; Fomin, Fedor et al. (2023). Two-sets cut-uncut on planar graphs. (external link)
• Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr et al. (2023). Lossy Kernelization of Same-Size Clustering. (external link)
• Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (2023). Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. (external link)
• Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin et al. (2023). Kernelization for Spreading Points. (external link)
• Fomin, Fedor; Golovach, Petr; Korhonen, Tuukka Matias Aleksanteri et al. (2023). Computing Paths of Large Rank in Planar Frameworks Deterministically. (external link)
• Arrighi, Emmanuel Jean Paul Pierre; Fomin, Fedor; Golovach, Petr et al. (2023). Kernelizing Temporal Exploration Problems. (external link)
• Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin et al. (2023). FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges. (external link)
• Sam, Emmanuel; Bergougnoux, Benjamin; Golovach, Petr et al. (2023). Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves. (external link)
• Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr et al. (2023). Parameterized Complexity of Feature Selection for Categorical Data Clustering. (external link)
• Fomin, Fedor; Golovach, Petr; Korhonen, Tuukka et al. (2023). Fixed-Parameter Tractability of Maximum Colored Path and Beyond. (external link)
• Fomin, Fedor; Golovach, Petr; Korhonen, Tuukka Matias Aleksanteri et al. (2023). Shortest Cycles With Monotone Submodular Costs. (external link)
• Fomin, Fedor; Fraigniaud, Pierre; Golovach, Petr (2023). Parameterized Complexity of Broadcasting in Graphs. (external link)
• Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (2023). Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. (external link)
• Fomin, Fedor; Golovach, Petr; Sagunov, Danil et al. (2023). Turán's Theorem Through Algorithmic Lens. (external link)
• Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (2023). Combing a Linkage in an Annulus. (external link)
• Sam, Emmanuel; Fellows, Michael Ralph; Rosamond, Frances et al. (2023). On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves. (external link)
• Fomin, Fedor; Golovach, Petr; Sagunov, Danil et al. (2023). Approximating Long Cycle Above Dirac's Guarantee. (external link)
• Fomin, Fedor; Golovach, Petr; Sau, Ignasi et al. (2023). Compound Logics for Modification Problems. (external link)
• Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr et al. (2023). How to find a good explanation for clustering?. (external link)

2022

• Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin et al. (2022). (Re)packing Equal Disks into Rectangle. (external link)
• Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre et al. (2022). Detours in Directed Graphs. (external link)
• Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr et al. (2022). How to Find a Good Explanation for Clustering?. (external link)
• Fomin, Fedor; Golovach, Petr; Sagunov, Danil et al. (2022). Algorithmic Extensions of Dirac's Theorem. (external link)
• Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin et al. (2022). Exact Exponential Algorithms for Clustering Problems. (external link)
• Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr et al. (2022). FPT Approximation for Fair Minimum-Load Clustering. (external link)
• Golovach, Petr; Lima, Paloma T.; Papadopoulos, Charis (2022). Graph Square Roots of Small Distance from Degree One Graphs. (external link)
• Brause, Christoph; Golovach, Petr; Martin, Barnaby et al. (2022). Partitioning H-free graphs of bounded diameter. (external link)
• Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr et al. (2022). Lossy Kernelization of Same-Size Clustering. (external link)
• Brause, Christoph; Golovach, Petr; Martin, Barnaby et al. (2022). Acyclic, star, and injective colouring: bounding the diameter^∗. (external link)
• Fomin, Fedor; Golovach, Petr; Sagunov, Danil et al. (2022). Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2022). Parameterized Complexity of Elimination Distance to First-Order Logic Properties. (external link)
• Fomin, Fedor; Golovach, Petr; Sagunov, Danil et al. (2022). Longest Cycle Above Erdös-Gallai Bound. (external link)
• Fomin, Fedor; Fraigniaud, Pierre; Golovach, Petr (2022). Present-biased optimization. (external link)
• Golovach, Petr; Paulusma, Daniël; van Leeuwen, Erik Jan (2022). Induced Disjoint Paths in AT-free graphs. (external link)
• Crespelle, Christophe Dominique; Golovach, Petr (2022). Cyclability in graph classes. (external link)

2021

• Golovach, Petr; Komusiewicz, Christian; Kratsch, Dieter et al. (2021). Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. (external link)
• Fomin, Fedor; Golovach, Petr (2021). Kernelization of Whitney Switches. (external link)
• Fomin, Fedor; Golovach, Petr; Purohit, Nidhi (2021). Parameterized Complexity of Categorical Clustering with Size Constraints. (external link)
• Chaplick, Steven; Fomin, Fedor; Golovach, Petr et al. (2021). Kernelization of Graph Hamiltonicity: Proper H-Graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2021). Can Romeo and Juliet Meet? or Rendezvous Games with Adversaries on Graphs. (external link)
• Brause, Christoph; Golovach, Petr; Martin, Barnaby et al. (2021). Acyclic, Star, and Injective Colouring: Bounding the Diameter. (external link)
• Fomin, Fedor; Golovach, Petr; Panolan, Fahad et al. (2021). Diverse Collections in Matroids and Graphs. (external link)
• Eiben, Eduard; Fomin, Fedor; Golovach, Petr et al. (2021). EPTAS for k-means Clustering of Affine Subspaces. (external link)
• Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr et al. (2021). Parameterized Complexity of Feature Selection for Categorical Data Clustering. (external link)
• Fomin, Fedor; Golovach, Petr (2021). Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Simonov, Kirill (2021). Parameterized k-Clustering: Tractability island. (external link)
• Fomin, Fedor; Fraigniaud, Pierre; Golovach, Petr (2021). Present-Biased Optimization. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2021). Parameterized Complexity of Elimination Distance to First-Order Logic Properties. (external link)
• Brause, Christoph; Golovach, Petr; Martin, Barnaby et al. (2021). Partitioning H-Free Graphs of Bounded Diameter. (external link)
• Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin et al. (2021). ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space. (external link)
• Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre et al. (2021). Parameterized Complexity of Directed Spanner Problems. (external link)

2020

• Fomin, Fedor; Golovach, Petr; Raymond, Jean-Florent (2020). On the Tractability of Optimization Problems on H-Graphs. (external link)
• Chaplick, Steven; Golovach, Petr; Hartmann, Tim et al. (2020). Recognizing Proper Tree-Graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Lochet, William et al. (2020). Parameterized Complexity of Directed Spanner Problems. (external link)
• Fomin, Fedor; Golovach, Petr; Jaffke, Lars et al. (2020). Diverse Pairs of Matchings. (external link)
• Golovach, Petr; Lima, Paloma T.; Papadopoulos, Charis (2020). Graph Square Roots of Small Distance from Degree One Graphs. (external link)
• Golovach, Petr; Krithika, R.; Sahu, Abhishek et al. (2020). Graph Hamiltonicity Parameterized by Proper Interval Deletion Set. (external link)
• Fomin, Fedor; Golovach, Petr (2020). Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2020). Going Far from Degeneracy. (external link)
• Fomin, Fedor; Golovach, Petr; Panolan, Fahad et al. (2020). Low-Rank Binary Matrix Approximation in Column-Sum Norm. (external link)
• Fomin, Fedor; Golovach, Petr (2020). Kernelization of Whitney Switches. (external link)
• Fomin, Fedor; Golovach, Petr; Stamoulis, Giannos et al. (2020). An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL. (external link)
• Fomin, Fedor; Golovach, Petr; Misra, Pranabendu et al. (2020). On the Complexity of Recovering Incidence Matrices. (external link)
• Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios (2020). Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. (external link)
• Golovach, Petr; Heggernes, Pinar; Lima, Paloma T. et al. (2020). Finding connected secluded subgraphs. (external link)
• Fomin, Fedor; Golovach, Petr; Panolan, Fahad (2020). Parameterized low-rank binary matrix approximation. (external link)
• Golovach, Petr; Heggernes, Pinar; Konstantinidis, Athanasios L. et al. (2020). Parameterized Aspects of Strong Subgraph Closure. (external link)
• Fomin, Fedor; Golovach, Petr; Simonov, Kirill (2020). Parameterized complexity of PCA. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2020). Parameterization Above a Multiplicative Guarantee . (external link)
• Fomin, Fedor; Golovach, Petr; Strømme, Torstein J. F. et al. (2020). Subgraph Complementation. (external link)

2019

• Golovach, Petr; Kratsch, Dieter; Liedloff, Mathieu et al. (2019). Enumeration and maximum number of minimal dominating sets for chordal graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2019). Spanning circuits in regular matroids. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2019). On the parameterized complexity of graph modification to first-order logic properties. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2019). Going Far From Degeneracy. (external link)
• Fomin, Fedor; Golovach, Petr; Simonov, Kirill (2019). Parameterized k-Clustering: Tractability Island. (external link)
• Crespelle, Christophe Dominique; Feghali, Carl; Golovach, Petr (2019). Cyclability in Graph Classes. (external link)
• Golovach, Petr; Johnson, Matthew; Martin, Barnaby et al. (2019). Surjective H-colouring: New hardness results. (external link)
• Fomin, Fedor; Golovach, Petr; Panolan, Fahad et al. (2019). Refined Complexity of PCA with Outliers. (external link)
• Golovach, Petr; Thilikos, Dimitrios M. (2019). Clustering to Given Connectivities. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2019). Approximation Schemes for Low-rank Binary Matrix Approximation Problems. (external link)
• Chaplick, Steven; Fomin, Fedor; Golovach, Petr et al. (2019). Kernelization of graph hamiltonicity: Proper H-graphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2019). Enumeration of Minimal Connected Dominating Sets for Chordal Graphs. (external link)
• Golovach, Petr; Kratsch, Dieter; Liedloff, Mathieu et al. (2019). Enumeration and maximum number of maximal irredundant sets for chordal graphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2019). Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2. (external link)
• Fomin, Fedor; Golovach, Petr; Panolan, Fahad et al. (2019). Editing to connected F-degree graph. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M (2019). Modification to planarity is fixed parameter tractable. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2019). Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. (external link)

2018

• Fomin, Fedor; Golovach, Petr; Raymond, Jean-Florent (2018). On the tractability of optimization problems on H-graphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Thomé de Lima, Paloma et al. (2018). Finding connected secluded subgraphs. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2018). Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. (external link)
• Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha et al. (2018). Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. (external link)
• Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket et al. (2018). Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. (external link)
• Fomin, Fedor; Golovach, Petr; Strømme, Torstein J. et al. (2018). Partial Complementation of Graphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Konstantinidis, Athanasios et al. (2018). Parameterized Aspects of Strong Subgraph Closure. (external link)
• Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr et al. (2018). Computing square roots of graphs with low maximum degree. (external link)
• Fomin, Fedor; Golovach, Petr; Panolan, Fahad (2018). Parameterized low-rank binary matrix approximation. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2018). Covering Vectors by Spaces: Regular Matroids. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2018). Structured connectivity augmentation. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (2018). Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs. (external link)

2017

• Golovach, Petr; Johnson, Matthew; Paulusma, Daniël et al. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. (external link)
• Golovach, Petr (2017). Editing to a connected graph of given degrees. (external link)
• Golovach, Petr; Kratsch, Dieter; Paulusma, Daniel et al. (2017). A linear kernel for finding square roots of almost planar graphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2017). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. (external link)
• Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha et al. (2017). Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. (external link)
• Golovach, Petr; Heggernes, Pinar; Lindzey, Nathan et al. (2017). On recognition of threshold tolerance graphs and their complements. (external link)
• Golovach, Petr; Paulusma, Daniël; Stewart, Iain (2017). Graph editing to a fixed target. (external link)
• Dabrowski, Konrad K.; Golovach, Petr; van 't Hof, Pim et al. (2017). Editing to a planar graph of given degrees. (external link)
• Golovach, Petr; Mertzios, George B. (2017). Graph editing to a given degree sequence. (external link)
• Belmonte, Remy; Fomin, Fedor; Golovach, Petr et al. (2017). Metric Dimension of Bounded Tree-length Graphs. (external link)
• Golovach, Petr; Johnson, Matthew; Martin, Barnaby et al. (2017). Surjective H-colouring: New hardness results. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2017). Structured Connectivity Augmentation. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2017). Spanning Circuits in Regular Matroids. (external link)
• Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha et al. (2017). Minimal dominating sets in interval graphs and trees. (external link)
• Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël et al. (2017). Finding Cactus Roots in Polynomial Time. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2017). Covering vectors by spaces: Regular matroids. (external link)
• Golovach, Petr; Kratsch, Dieter; Liedloff, Mathieu et al. (2017). Enumeration and maximum number of maximal irredundant sets for chordal graphs. (external link)
• Golovach, Petr; Kratsch, Dieter; Sayadi, Mohamed Yosri (2017). Enumeration of maximal irredundant sets for claw-free graphs. (external link)
• Golovach, Petr; Kamiński,, Marcin; Maniatis, Spyridon et al. (2017). The parameterized complexity of graph cyclability. (external link)

2016

• Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr et al. (2016). Parameterized algorithms for finding square roots. (external link)
• Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël et al. (2016). Squares of low clique number. (external link)
• Golovach, Petr; Paulusma, Daniël; van Leeuwen, Erik Jan (2016). Induced disjoint paths in circular-arc graphs in linear time. (external link)
• Bliznets, Ivan; Fomin, Fedor; Golovach, Petr et al. (2016). Parameterized Complexity of Superstring Problems. (external link)
• Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr (2016). Parameterized complexity of the anchored k-core problem for directed graphs. (external link)
• Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël et al. (2016). Finding cactus roots in polynomial time. (external link)
• Fomin, Fedor; Golovach, Petr; Karpov, Nikolay et al. (2016). Parameterized complexity of secluded connectivity problems. (external link)
• Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël et al. (2016). A linear kernel for finding square roots of almost planar graphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (2016). Enumerating minimal connected dominating sets in graphs of bounded chordality. (external link)
• Dabrowski, Konrad K.; Golovach, Petr; van 't Hof, Pim et al. (2016). Editing to Eulerian graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Panolan, Fahad et al. (2016). Editing to connected f-degree graph. (external link)
• Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou M. et al. (2016). Enumerating minimal dominating sets in chordal bipartite graphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (2016). Enumeration and maximum number of minimal connected vertex covers in graphs. (external link)
• Golovach, Petr; Mertzios, George B. (2016). Graph editing to a given degree sequence. (external link)
• Abramovskaya, Tatjana V.; Fomin, Fedor; Golovach, Petr et al. (2016). How to hunt an invisible rabbit on a graph. (external link)

2015

• Golovach, Petr; Heggernes, Pinar; van' t Hof, Pim et al. (2015). Hadwiger number of graphs with small chordality. (external link)
• Golovach, Petr; Golovach, Petr A; van'T Hof, Pim et al. (2015). Editing to a Connected Graph of Given Degrees. (external link)
• Broersma, Hajo; Fiala, Jiří; Golovach, Petr et al. (2015). Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs665. (external link)
• Golovach, Petr; Paulusma, Daniël; van Leeuwen, Erik Jan (2015). Induced disjoint paths in claw-free graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Nederlof, Jesper et al. (2015). Minimizing Rosenthal potential in multicast games. (external link)
• Dabrowski, Konrad K; Golovach, Petr; van'T Hof, Pim et al. (2015). Editing to a planar graph of given degrees. (external link)
• Couturier, Jean-François; Golovach, Petr; Kratsch, Dieter et al. (2015). List coloring in the absence of a linear forest. (external link)
• Fomin, Fedor; Golovach, Petr; Karpov, Nikolay et al. (2015). Parameterized complexity of secluded connectivity problems. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (2015). Enumerating minimal connected dominating sets in graphs of bounded chordality. (external link)
• Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim et al. (2015). Modifying a graph using vertex elimination. (external link)
• Belmonte, Remy; Fomin, Fedor; Golovach, Petr et al. (2015). Metric dimension of bounded width graphs. (external link)
• Bliznets, Ivan; Fomin, Fedor; Golovach, Petr et al. (2015). Parameterized complexity of superstring problems. (external link)
• Golovach, Petr (2015). Editing to a Graph of Given Degrees. (external link)
• Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim et al. (2015). Hadwiger number of graphs with small chordality. (external link)
• Golovach, Petr; Paulusma, Daniël; Ries, Bernard (2015). Coloring graphs characterized by a forbidden subgraph. (external link)
• Golovach, Petr; Requile, Clement; Thilikos, Dimitrios M. (2015). Variants of plane diameter completion. (external link)
• Golovach, Petr; Heggernes, Pinar; Kante, Mamadou et al. (2015). Output-polynomial enumeration on graphs of bounded (local) linear mim-width. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2015). An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. (external link)

2014

• Fomin, Fedor; Golovach, Petr (2014). Parameterized complexity of connected even/odd subgraph problems. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2014). Subset feedback vertex sets in chordal graphs. (external link)
• Golovach, Petr; Paulusma, Daniel (2014). List coloring in the absence of two subgraphs. (external link)
• Golovach, Petr; Paulusma, Daniël; Song, Jian (2014). Coloring graphs without short cycles and long induced paths. (external link)
• Dabrowski, Konrad K.; Golovach, Petr; Paulusma, Daniël (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2014). An incremental polynomial time Algorithm to enumerate all minimal edge dominating sets. (external link)
• Fomin, Fedor; Golovach, Petr (2014). Long circuits and large euler subgraphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2014). Finding clubs in graph classes. (external link)
• Belmonte, Rémy; Golovach, Petr; Heggernes, Pinar et al. (2014). Detecting fixed patterns in chordal graphs in polynomial time. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2014). Almost optimal lower bounds for problems parameterized by clique-width. (external link)
• Biro, Peter; Bomhoff, Matthijs; Golovach, Petr et al. (2014). Solutions for the stable roommates problem with payments. (external link)
• Basavaraju, Manu; Fomin, Fedor; Golovach, Petr et al. (2014). Connecting vertices by independent trees. (external link)
• Basavaraju, Manu; Fomin, Fedor; Golovach, Petr et al. (2014). Parameterized algorithms to preserve connectivity. (external link)
• Golovach, Petr; Paulusma, Daniël; van Leeuwen, Erik Jan (2014). Induced disjoint paths in circular-arc graphs in linear time. (external link)
• Golovach, Petr; Heggernes, Pinar; Lindzey, Nathan et al. (2014). Recognizing Threshold Tolerance Graphs in O(n^2) Time. (external link)
• Dabrowski, Konrad K.; Golovach, Petr; van 't Hof, Pim et al. (2014). Editing to Eulerian graphs. (external link)
• Golovach, Petr (2014). Editing to a Graph of Given Degrees. (external link)
• Golovach, Petr; Paulusma, Daniël; Kaminski, Marcin et al. (2014). Lift-contractions. (external link)
• Golovach, Petr; Paulusma, Daniël; Song, Jian (2014). Closing complexity gaps for coloring problems on H-free graphs. (external link)
• Golovach, Petr; Kaminski, Marcin; Maniatis, Spyridon et al. (2014). The parameterized complexity of graph cyclability. (external link)
• Belmonte, Rémy; Golovach, Petr; van 't Hof, Pim et al. (2014). Parameterized complexity of three edge contraction problems with degree constraints. (external link)
• dos Santos, Vinicius; Golovach, Petr; Heggernes, Pinar et al. (2014). On Recognition of Threshold Tolerance Graphs and their Complements. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2014). An exact algorithm for Subset Feedback Vertex Set on chordal graphs. (external link)

2013

• Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr (2013). Preventing unraveling in social networks gets harder. (external link)
• Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr (2013). Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. (external link)
• Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim et al. (2013). Modifying a Graph Using Vertex Elimination. (external link)
• Broersma, Hajo; Fomin, Fedor; Golovach, Petr et al. (2013). Three complexity results on coloring Pk-free graphs. (external link)
• Golovach, Petr; van 't Hof, Pim; Paulusma, Daniël (2013). Obtaining planarity by contracting few edges. (external link)
• Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim et al. (2013). Choosability on H-free graphs. (external link)
• Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël (2013). Detecting induced minors in AT-free graphs. (external link)
• Broersma, Hajo; Golovach, Petr; Patel, Viresh (2013). Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. (external link)

2012

• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2012). An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Pralat, Pawel (2012). Cops and robber with constraints. (external link)
• Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim et al. (2012). How to Eliminate a Graph. (external link)
• Golovach, Petr; Heggernes, Pinar; Mihai, Rodica (2012). Edge search number of cographs. (external link)
• Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr et al. (2012). Parameterized complexity of the spanning tree congestion problem. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel (2012). Cops and robber game without recharging. (external link)
• Golovach, Petr; van 't Hof, Pim; Paulusma, Daniel (2012). Obtaining planarity by contracting few edges. (external link)
• Fomin, Fedor; Gaspers, Serge; Golovach, Petr et al. (2012). k-Gap Interval Graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Nederlof, Jesper et al. (2012). Minimizing Rosenthal potential in multicast games. (external link)
• Golovach, Petr; Paulusma, Daniel; Jian, Song (2012). Closing Complexity Gaps for Coloring Problems on H-Free Graphs. (external link)
• Golovach, Petr; Paulusma, Daniel; Ries, Bernard (2012). Coloring Graphs Characterized by a Forbidden Subgraph. (external link)
• Golovach, Petr; Kratsch, Dieter; Paulusma, Daniel (2012). Detecting Induced Minors in AT-Free Graphs. (external link)

2011

• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2011). Bandwidth on AT-free graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Kratochvil, Jan et al. (2011). Branch and Recharge: Exact Algorithms for Generalized Domination. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2011). Contraction obstructions for treewidth. (external link)
• Fomin, Fedor; Golovach, Petr; van Leeuwen, Erik Jan (2011). Spanners of bounded degree graphs. (external link)
• Dragan, Feodor F.; Fomin, Fedor; Golovach, Petr (2011). Approximation of minimum weight spanners for sparse graphs. (external link)
• Dragan, Feodor F.; Fomin, Fedor; Golovach, Petr (2011). Spanners in sparse graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel (2011). Guard games on graphs: Keep the intruder out!. (external link)
• Fomin, Fedor; Golovach, Petr; Hall, Alex et al. (2011). How to Guard a Graph?. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (2011). Approximating width parameters of hypergraphs with excluded minors. (external link)

2010

• Fiala, Jiří; Golovach, Petr (2010). Complexity of the packing coloring problem for trees. (external link)
• Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel et al. (2010). Intractability of clique-width parameterizations. (external link)
• Fomin, Fedor; Golovach, Petr; Kratochvil, Jan et al. (2010). Pursuing a fast robber on a graph. (external link)

2009

• Fomin, Fedor; Golovach, Petr; Kratochvil, Jan et al. (2009). Sort and Search: Exact algorithms for generalized domination. (external link)
• Bonato, Anthony; Golovach, Petr; Hahn, Gena et al. (2009). The capture time of a graph. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (2009). Approximating Acyclicity Parameters of Sparse Hypergraphs. (external link)
• Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter et al. (2009). Bandwidth on AT-Free Graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (2009). Contraction Bidimensionality: The Accurate Picture. (external link)
• Golovach, Petr; Thilikos, Dimitrios M. (2009). Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms. (external link)
• Fiala, Jiří; Golovach, Petr; Kratochvil, Jan (2009). Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. (external link)
• Golovach, Petr; Kratochvil, Jan; Suchy, Ondra (2009). Parameterized Complexity of Generalized Domination Problems. (external link)
• Golovach, Petr; Kaminski, M.; Paulusma, Daniel et al. (2009). Induced Packing of Odd Cycles in a Planar Graph. (external link)
• Golovach, Petr; Heggernes, Pinar (2009). Choosability of P5-free graphs. (external link)
• Broersma, Hajo; Fomin, Fedor; Golovach, Petr et al. (2009). Three Complexity Results on Coloring Pk-Free Graphs. (external link)

2008

• Dragan, Feodor; Fomin, Fedor; Golovach, Petr (2008). Spanners in sparse graphs. (external link)
• Fiala, Jiri; Golovach, Petr (2008). Complexity of the packing coloring problem for trees. (external link)
• Golovach, Petr; Villanger, Yngve (2008). Parameterized complexity for domination problems on degenerate graphs. (external link)
• Fiala, Jiri; Golovach, Petr; Kratochvil, Jan (2008). Distance constrained labeling of trees. (external link)
• Fiala, Jiri; Golovach, Petr; Kratochvil, Jan (2008). Computational complexity of the distance constrained labeling problem for trees. (external link)
• Golovach, Petr; Kratochvil, Jan (2008). Generalized domination in degenerate graphs: a complete dichotomy of computational complexity. (external link)
• Dragan, Feodor; Fomin, Fedor; Golovach, Petr (2008). A PTAS for the sparsest spanners problem on apex-minor-free graphs. (external link)
• Fomin, Fedor; Golovach, Petr; Hall, Alex et al. (2008). How to guard a graph?. (external link)
• Fomin, Fedor; Golovach, Petr; Kratochvil, Jan (2008). On tractability cops and robbers game. (external link)

2007

• Broersma, Hajo; Fomin, Fedor; Golovach, Petr et al. (2007). Backbone colorings for graphs: Tree and path backbones. (external link)
• Golovach, Petr; Fomin, Fedor; Kratochvil, Jan et al. (2007). Branch and Recharge: Exact Algorithms for Generalized Domination. (external link)
• Golovach, Petr; Kratochvil, Jan (2007). Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs. (external link)

See a complete overview of publications in Cristin.