Home
Petr Golovach's picture

Petr Golovach

Researcher
  • E-mailPetr.Golovach@uib.no
  • Phone+47 55 58 43 85
  • Visitor Address
    HIB - Thormøhlensgt. 55
  • Postal Address
    Postboks 7803
    5020 Bergen
Academic article
  • Golovach, Petr; Heggernes, Pinar; Konstantinidis, Athanasios; Lima, Paloma T.; Papadopoulos, Charis. 2020. Parameterized Aspects of Strong Subgraph Closure. Algorithmica.
  • Golovach, Petr; Johnson, Matthew; Martin, Barnaby; Paulusma, Daniël; Stewart, Anthony. 2019. Surjective H-colouring: New hardness results. Computability - The Journal of the Assosiation. 27-42.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2019. Spanning circuits in regular matroids. ACM Transactions on Algorithms (TALG).
  • Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill. 2019. Refined Complexity of PCA with Outliers. Proceedings of Machine Learning Research (PMLR). 5818-5826.
  • Fomin, Fedor; Golovach, Petr; Simonov, Kirill. 2019. Parameterized k-Clustering: Tractability Island. Leibniz International Proceedings in Informatics. 14:1-14:15.
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2019. On the parameterized complexity of graph modification to first-order logic properties. Theory of Computing Systems. 251-271.
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2019. Modification to planarity is fixed parameter tractable. Leibniz International Proceedings in Informatics. 28:1-28:17.
  • Chaplick, Steven; Fomin, Fedor; Golovach, Petr; Knop, Dusan; Zeman, Peter. 2019. Kernelization of graph hamiltonicity: Proper H-graphs. Lecture Notes in Computer Science (LNCS). 296-310.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav. 2019. Going Far From Degeneracy. Leibniz International Proceedings in Informatics. 47:1-47:14.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza. 2019. Enumeration of Minimal Connected Dominating Sets for Chordal Graphs. Discrete Applied Mathematics.
  • Golovach, Petr; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri. 2019. Enumeration and maximum number of minimal dominating sets for chordal graphs. Theoretical Computer Science. 41-52.
  • Golovach, Petr; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri. 2019. Enumeration and maximum number of maximal irredundant sets for chordal graphs. Discrete Applied Mathematics. 69-85.
  • Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Saurabh, Saket. 2019. Editing to connected F-degree graph. SIAM Journal on Discrete Mathematics. 795-836.
  • Crespelle, Christophe Dominique; Feghali, Carl; Golovach, Petr. 2019. Cyclability in Graph Classes. Leibniz International Proceedings in Informatics. 16:1-16:13.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav. 2019. Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. Leibniz International Proceedings in Informatics. 59:1-59:13.
  • Golovach, Petr; Thilikos, Dimitrios M. 2019. Clustering to Given Connectivities. Leibniz International Proceedings in Informatics. 18:1-18:17.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket. 2019. Approximation Schemes for Low-rank Binary Matrix Approximation Problems. ACM Transactions on Algorithms (TALG). 12:1-12:39.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lima, Paloma T.; Paulusma, Daniel. 2019. Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2. Algorithmica. 2795-2828.
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2018. Structured connectivity augmentation. SIAM Journal on Discrete Mathematics. 2612-2635.
  • Fomin, Fedor; Golovach, Petr; Strømme, Torstein J.; Thilikos, Dimitrios. 2018. Partial Complementation of Graphs. Leibniz International Proceedings in Informatics. 21:1-21:13.
  • Fomin, Fedor; Golovach, Petr; Panolan, Fahad. 2018. Parameterized low-rank binary matrix approximation. Leibniz International Proceedings in Informatics. 1-16.
  • Golovach, Petr; Heggernes, Pinar; Konstantinidis, Athanasios; T. Lima, Paloma; Papadopoulos, Charis. 2018. Parameterized Aspects of Strong Subgraph Closure. Leibniz International Proceedings in Informatics. 23:1-23:13.
  • Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve Hortemo; Villanger, Yngve. 2018. Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Algorithmica. 714-741.
  • Fomin, Fedor; Golovach, Petr; Raymond, Jean-Florent. 2018. On the tractability of optimization problems on H-graphs. Leibniz International Proceedings in Informatics. 1-14.
  • Golovach, Petr; Heggernes, Pinar; Thomé de Lima, Paloma; Montealegre, Pedro. 2018. Finding connected secluded subgraphs. Leibniz International Proceedings in Informatics. 1-13.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter. 2018. Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs. European journal of combinatorics (Print). 132-147.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2018. Covering Vectors by Spaces: Regular Matroids. SIAM Journal on Discrete Mathematics. 2512-2565.
  • Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony. 2018. Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics. 93-101.
  • Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav. 2018. Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 262-273.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav. 2018. Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG). 27 pages.
  • Golovach, Petr; Kamiński,, Marcin; Maniatis, Spyridon; Thilikos, Dimitrios M. 2017. The parameterized complexity of graph cyclability. SIAM Journal on Discrete Mathematics. 511-541.
  • Golovach, Petr; Johnson, Matthew; Martin, Barnaby; Paulusma, Daniel; Stewart, Anthony. 2017. Surjective H-colouring: New hardness results. Lecture Notes in Computer Science (LNCS). 270-281.
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2017. Structured Connectivity Augmentation. Leibniz International Proceedings in Informatics.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2017. Spanning Circuits in Regular Matroids. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1433-1441.
  • Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve Hortemo; Villanger, Yngve. 2017. Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Algorithmica. 714-741.
  • Golovach, Petr; Heggernes, Pinar; Lindzey, Nathan; McConnell, Ross M.; dos Santos, Vínicius Fernandes; Spinrad, Jeremy P.; Szwarcfiter, Jayme Luiz. 2017. On recognition of threshold tolerance graphs and their complements. Discrete Applied Mathematics. 171-180.
  • Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Villanger, Yngve. 2017. Minimal dominating sets in interval graphs and trees. Discrete Applied Mathematics. 162-170.
  • Belmonte, Remy; Fomin, Fedor; Golovach, Petr; Ramanujan, M. S. 2017. Metric Dimension of Bounded Tree-length Graphs. SIAM Journal on Discrete Mathematics. 1217-1243.
  • Golovach, Petr; Mertzios, George B. 2017. Graph editing to a given degree sequence. Theoretical Computer Science. 1-12.
  • Golovach, Petr; Paulusma, Daniël; Stewart, Iain. 2017. Graph editing to a fixed target. Discrete Applied Mathematics. 181-190.
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony. 2017. Finding Cactus Roots in Polynomial Time. Theory of Computing Systems. 1-18.
  • Golovach, Petr; Kratsch, Dieter; Sayadi, Mohamed Yosri. 2017. Enumeration of maximal irredundant sets for claw-free graphs. Lecture Notes in Computer Science (LNCS). 297-309.
  • Golovach, Petr; Kratsch, Dieter; Liedloff, Mathieu; Sayadi, Mohamed Yosri. 2017. Enumeration and maximum number of maximal irredundant sets for chordal graphs. Lecture Notes in Computer Science (LNCS). 289-302.
  • Dabrowski, Konrad K.; Golovach, Petr; van 't Hof, Pim; Paulusma, Daniël; Thilikos, Dimitrios M. 2017. Editing to a planar graph of given degrees. Journal of computer and system sciences (Print). 168-182.
  • Golovach, Petr. 2017. Editing to a connected graph of given degrees. Information and Computation. 131-147.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2017. Covering vectors by spaces: Regular matroids. Leibniz International Proceedings in Informatics. 1-15.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lima, Paloma; Paulusma, Daniël. 2017. Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Lecture Notes in Computer Science (LNCS). 275-288.
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniel; Stewart, Anthony. 2017. A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science. 36-47.
  • Golovach, Petr; Johnson, Matthew; Paulusma, Daniël; Song, Jian. 2017. A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory. 331-363.
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony. 2016. Squares of low clique number. Electronic Notes in Discrete Mathematics. 195-198.
  • Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr. 2016. Parameterized complexity of the anchored k-core problem for directed graphs. Information and Computation. 11-22.
  • Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S. 2016. Parameterized complexity of secluded connectivity problems. Theory of Computing Systems. 1-25.
  • Cochefert, Manfred; Couturier, Jean-François; Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël. 2016. Parameterized algorithms for finding square roots. Algorithmica. 602-629.
  • Bliznets, Ivan; Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S.; Saurabh, Saket. 2016. Parameterized Complexity of Superstring Problems. Algorithmica. 1-16.
  • Golovach, Petr; Paulusma, Daniël; van Leeuwen, Erik Jan. 2016. Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science. 70-83.
  • Abramovskaya, Tatjana V.; Fomin, Fedor; Golovach, Petr; Pilipczuk, Michal Pawel. 2016. How to hunt an invisible rabbit on a graph. European journal of combinatorics (Print). 12-26.
  • Golovach, Petr; Mertzios, George B. 2016. Graph editing to a given degree sequence. Lecture Notes in Computer Science (LNCS). 177-191.
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony. 2016. Finding cactus roots in polynomial time. Lecture Notes in Computer Science (LNCS). 361-372.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter. 2016. Enumeration and maximum number of minimal connected vertex covers in graphs. Lecture Notes in Computer Science (LNCS). 235-247.
  • Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve. 2016. Enumerating minimal dominating sets in chordal bipartite graphs. Discrete Applied Mathematics. 30-36.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter. 2016. Enumerating minimal connected dominating sets in graphs of bounded chordality. Theoretical Computer Science. 63-75.
  • Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Saurabh, Saket. 2016. Editing to connected f-degree graph. Leibniz International Proceedings in Informatics. 1-15.
  • Dabrowski, Konrad K.; Golovach, Petr; van 't Hof, Pim; Paulusma, Daniël. 2016. Editing to Eulerian graphs. Journal of computer and system sciences (Print). 213-228.
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël; Stewart, Antony. 2016. A linear kernel for finding square roots of almost planar graphs. Leibniz International Proceedings in Informatics. 4.1-4.14.
  • Golovach, Petr; Requile, Clement; Thilikos, Dimitrios M. 2015. Variants of plane diameter completion. Leibniz International Proceedings in Informatics. 30-42.
  • Bliznets, Ivan; Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S; Saurabh, Saket. 2015. Parameterized complexity of superstring problems. Lecture Notes in Computer Science (LNCS). 89-99.
  • Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S. 2015. Parameterized complexity of secluded connectivity problems. Leibniz International Proceedings in Informatics. 408-419.
  • Golovach, Petr; Heggernes, Pinar; Kante, Mamadou; Kratsch, Dieter; Sæther, Sigve Hortemo; Villanger, Yngve. 2015. Output-polynomial enumeration on graphs of bounded (local) linear mim-width. Lecture Notes in Computer Science (LNCS). 248-258.
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Manne, Fredrik; Paulusma, Daniël; Pilipczuk, Michal Pawel. 2015. Modifying a graph using vertex elimination. Algorithmica. 99-125.
  • Fomin, Fedor; Golovach, Petr; Nederlof, Jesper; Pilipczuk, Michal Pawel. 2015. Minimizing Rosenthal potential in multicast games. Theory of Computing Systems. 81-96.
  • Belmonte, Remy; Fomin, Fedor; Golovach, Petr; Ramanujan, MS. 2015. Metric dimension of bounded width graphs. Lecture Notes in Computer Science (LNCS). 115-126.
  • Couturier, Jean-François; Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël. 2015. List coloring in the absence of a linear forest. Algorithmica. 21-35.
  • Broersma, Hajo; Fiala, Jiří; Golovach, Petr; Kaiser, Tomas; Paulusma, Daniël; Proskurowski, Andrzej. 2015. Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs665. Journal of Graph Theory. 282-299.
  • Golovach, Petr; Paulusma, Daniël; van Leeuwen, Erik Jan. 2015. Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics. 348-375.
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Paul, Christophe. 2015. Hadwiger number of graphs with small chordality. SIAM Journal on Discrete Mathematics. 1427-1451.
  • Golovach, Petr; Heggernes, Pinar; van' t Hof, Pim; Paul, Christophe. 2015. Hadwiger number of graphs with small chordality. Lecture Notes in Computer Science (LNCS). 201-213.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter. 2015. Enumerating minimal connected dominating sets in graphs of bounded chordality. Leibniz International Proceedings in Informatics. 307-318.
  • Dabrowski, Konrad K; Golovach, Petr; van'T Hof, Pim; Paulusma, Daniel; Thilikos, Dimitrios M. 2015. Editing to a planar graph of given degrees. Lecture Notes in Computer Science (LNCS). 143-156.
  • Golovach, Petr. 2015. Editing to a Graph of Given Degrees. Theoretical Computer Science. 72-84.
  • Golovach, Petr; Golovach, Petr A; van'T Hof, Pim; Paulusma, Daniel; Thilikos, Dimitrios M. 2015. Editing to a Connected Graph of Given Degrees. Lecture Notes in Computer Science (LNCS). 324-335.
  • Golovach, Petr; Paulusma, Daniël; Ries, Bernard. 2015. Coloring graphs characterized by a forbidden subgraph. Discrete Applied Mathematics. 101-110.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve. 2015. An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Algorithmica. 836-859.
  • Golovach, Petr; Kaminski, Marcin; Maniatis, Spyridon; Thilikos, Dimitrios M. 2014. The parameterized complexity of graph cyclability. Lecture Notes in Computer Science (LNCS). 492-504.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; SaeiDinvar, Reza. 2014. Subset feedback vertex sets in chordal graphs. Journal of Discrete Algorithms. 7-15.
  • Biro, Peter; Bomhoff, Matthijs; Golovach, Petr; Kern, Walter; Paulusma, Daniël. 2014. Solutions for the stable roommates problem with payments. Theoretical Computer Science. 53-61.
  • Golovach, Petr; Heggernes, Pinar; Lindzey, Nathan; McConnell, Ross; Fernandes dos Santos, Vinicius; Spinrad, Jeremy. 2014. Recognizing Threshold Tolerance Graphs in O(n^2) Time. Lecture Notes in Computer Science (LNCS). 214-224.
  • Belmonte, Rémy; Golovach, Petr; van 't Hof, Pim; Paulusma, Daniël. 2014. Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica. 473-497.
  • Fomin, Fedor; Golovach, Petr. 2014. Parameterized complexity of connected even/odd subgraph problems. Journal of computer and system sciences (Print). 157-179.
  • Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Misra, Pranabendu; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket. 2014. Parameterized algorithms to preserve connectivity. Lecture Notes in Computer Science (LNCS). 800-811.
  • dos Santos, Vinicius; Golovach, Petr; Heggernes, Pinar; Nathan, Lindzey; McConnell, Ross; Spinrad, Jeremy. 2014. On Recognition of Threshold Tolerance Graphs and their Complements. Lecture Notes in Computer Science (LNCS). 214-224.
  • Fomin, Fedor; Golovach, Petr. 2014. Long circuits and large euler subgraphs. SIAM Journal on Discrete Mathematics. 878-892.
  • Golovach, Petr; Paulusma, Daniel. 2014. List coloring in the absence of two subgraphs. Discrete Applied Mathematics. 123-130.
  • Golovach, Petr; Paulusma, Daniël; Kaminski, Marcin; Thilikos, Dimitrios M. 2014. Lift-contractions. European journal of combinatorics (Print). 286-296.
  • Golovach, Petr; Paulusma, Daniël; van Leeuwen, Erik Jan. 2014. Induced disjoint paths in circular-arc graphs in linear time. Lecture Notes in Computer Science (LNCS). 225-237.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash. 2014. Finding clubs in graph classes. Discrete Applied Mathematics. 57-65.
  • Golovach, Petr. 2014. Editing to a Graph of Given Degrees. Lecture Notes in Computer Science (LNCS). 196-207.
  • Dabrowski, Konrad K.; Golovach, Petr; van 't Hof, Pim; Paulusma, Daniël. 2014. Editing to Eulerian graphs. Leibniz International Proceedings in Informatics. 97-108.
  • Belmonte, Rémy; Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Kaminski, Marcin; Paulusma, Daniël. 2014. Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica. 501-521.
  • Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket. 2014. Connecting vertices by independent trees. Leibniz International Proceedings in Informatics. 73-84.
  • Dabrowski, Konrad K.; Golovach, Petr; Paulusma, Daniël. 2014. Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science. 34-43.
  • Golovach, Petr; Paulusma, Daniël; Song, Jian. 2014. Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics. 107-120.
  • Golovach, Petr; Paulusma, Daniël; Song, Jian. 2014. Closing complexity gaps for coloring problems on H-free graphs. Information and Computation. 204-214.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve. 2014. An incremental polynomial time Algorithm to enumerate all minimal edge dominating sets. Algorithmica. 836-859.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza. 2014. An exact algorithm for Subset Feedback Vertex Set on chordal graphs. Journal of Discrete Algorithms. 7-15.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2014. Almost optimal lower bounds for problems parameterized by clique-width. SIAM journal on computing (Print). 1541-1563.
  • Broersma, Hajo; Golovach, Petr; Patel, Viresh. 2013. Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Theoretical Computer Science. 69-84.
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Paulusma, Daniël. 2013. Three complexity results on coloring Pk-free graphs. European journal of combinatorics (Print). 609-619.
  • Golovach, Petr; van 't Hof, Pim; Paulusma, Daniël. 2013. Obtaining planarity by contracting few edges. Theoretical Computer Science. 38-46.
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Manne, Fredrik; Paulusma, Daniël; Pilipczuk, Michal Pawel. 2013. Modifying a Graph Using Vertex Elimination. Algorithmica.
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël. 2013. Detecting induced minors in AT-free graphs. Theoretical Computer Science. 20-32.
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Paulusma, Daniel. 2013. Choosability on H-free graphs. Information Processing Letters. 107-110.
  • Fomin, Fedor; Gaspers, Serge; Golovach, Petr; Suchan, Karol; Szeider, Stefan; van Leeuwen, Erik Jan; Vatshelle, Martin; Villanger, Yngve. 2012. k-Gap Interval Graphs. Lecture Notes in Computer Science (LNCS). 350-361.
  • Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan. 2012. Parameterized complexity of the spanning tree congestion problem. Algorithmica. 85-111.
  • Golovach, Petr; van 't Hof, Pim; Paulusma, Daniel. 2012. Obtaining planarity by contracting few edges. Lecture Notes in Computer Science (LNCS). 455-466.
  • Fomin, Fedor; Golovach, Petr; Nederlof, Jesper; Pilipczuk, Michal Pawel. 2012. Minimizing Rosenthal potential in multicast games. Lecture Notes in Computer Science (LNCS).
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Manne, Fredrik; Paulusma, Daniel; Pilipczuk, Michal Pawel. 2012. How to Eliminate a Graph. Lecture Notes in Computer Science (LNCS). 320-331.
  • Golovach, Petr; Heggernes, Pinar; Mihai, Rodica. 2012. Edge search number of cographs. Discrete Applied Mathematics. 734-743.
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniel. 2012. Detecting Induced Minors in AT-Free Graphs. Lecture Notes in Computer Science (LNCS). 495-505.
  • Fomin, Fedor; Golovach, Petr; Pralat, Pawel. 2012. Cops and robber with constraints. SIAM Journal on Discrete Mathematics. 571-590.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel. 2012. Cops and robber game without recharging. Theory of Computing Systems. 611-620.
  • Golovach, Petr; Paulusma, Daniel; Ries, Bernard. 2012. Coloring Graphs Characterized by a Forbidden Subgraph. Lecture Notes in Computer Science (LNCS). 443-454.
  • Golovach, Petr; Paulusma, Daniel; Jian, Song. 2012. Closing Complexity Gaps for Coloring Problems on H-Free Graphs. Lecture Notes in Computer Science (LNCS). 14-23.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; SaeiDinvar, Reza. 2012. An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs. Lecture Notes in Computer Science (LNCS). 85-96.
  • Fomin, Fedor; Golovach, Petr; van Leeuwen, Erik Jan. 2011. Spanners of bounded degree graphs. Information Processing Letters. 142-144.
  • Dragan, Feodor F.; Fomin, Fedor; Golovach, Petr. 2011. Spanners in sparse graphs. Journal of computer and system sciences (Print). 1108-1119.
  • Fomin, Fedor; Golovach, Petr; Hall, Alex; Mihalák, Matúš; Vicari, Elias; Widmayer, Peter. 2011. How to Guard a Graph? Algorithmica. 839-856.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel. 2011. Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 6484-6497.
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2011. Contraction obstructions for treewidth. Journal of combinatorial theory. Series B (Print). 302-314.
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2011. Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica. 252-273.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket. 2011. Bandwidth on AT-free graphs. Theoretical Computer Science. 7001-7008.
  • Dragan, Feodor F.; Fomin, Fedor; Golovach, Petr. 2011. Approximation of minimum weight spanners for sparse graphs. Theoretical Computer Science. 846-852.
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2011. Approximating width parameters of hypergraphs with excluded minors. SIAM Journal on Discrete Mathematics. 1331-1348.
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Nisse, Nicolas; Suchan, Karol. 2010. Pursuing a fast robber on a graph. Theoretical Computer Science. 1167-1181.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2010. Intractability of clique-width parameterizations. SIAM journal on computing (Print). 1941-1956.
  • Fiala, Jiří; Golovach, Petr. 2010. Complexity of the packing coloring problem for trees. Discrete Applied Mathematics. 771-778.
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Paulusma, Daniel. 2009. Three Complexity Results on Coloring Pk-Free Graphs. Lecture Notes in Computer Science (LNCS). 95-104.
  • Bonato, Anthony; Golovach, Petr; Hahn, Gena; Kratochvil, Jan. 2009. The capture time of a graph. Discrete Mathematics. 5588-5595.
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2009. Sort and Search: Exact algorithms for generalized domination. Information Processing Letters. 795-798.
  • Golovach, Petr; Thilikos, Dimitrios M. 2009. Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms. Lecture Notes in Computer Science (LNCS). 210-221.
  • Golovach, Petr; Kratochvil, Jan; Suchy, Ondra. 2009. Parameterized Complexity of Generalized Domination Problems. Lecture Notes in Computer Science (LNCS). 133-142.
  • Fiala, Jiří; Golovach, Petr; Kratochvil, Jan. 2009. Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. Lecture Notes in Computer Science (LNCS). 221-230.
  • Golovach, Petr; Kaminski, M.; Paulusma, Daniel; Thilikos, Dimitrios M. 2009. Induced Packing of Odd Cycles in a Planar Graph. Lecture Notes in Computer Science (LNCS). 514-523.
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios. 2009. Contraction Bidimensionality: The Accurate Picture. Lecture Notes in Computer Science (LNCS). 706-717.
  • Golovach, Petr; Heggernes, Pinar. 2009. Choosability of P5-free graphs. Lecture Notes in Computer Science (LNCS). 382-391.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket. 2009. Bandwidth on AT-Free Graphs. Lecture Notes in Computer Science (LNCS). 573-582.
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios. 2009. Approximating Acyclicity Parameters of Sparse Hypergraphs. Leibniz International Proceedings in Informatics. 445-456.
  • Dragan, Feodor; Fomin, Fedor; Golovach, Petr. 2008. Spanners in sparse graphs. Lecture Notes in Computer Science (LNCS). 597-608.
  • Golovach, Petr; Villanger, Yngve. 2008. Parameterized complexity for domination problems on degenerate graphs. Lecture Notes in Computer Science (LNCS). 195-205.
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan. 2008. On tractability cops and robbers game. IFIP International Federation for Information Processing. 171-185.
  • Fomin, Fedor; Golovach, Petr; Hall, Alex; Mihalak, Matus; Vicari, Elias; Widmayer, Peter. 2008. How to guard a graph? Lecture Notes in Computer Science (LNCS). 318-239.
  • Golovach, Petr; Kratochvil, Jan. 2008. Generalized domination in degenerate graphs: a complete dichotomy of computational complexity. Lecture Notes in Computer Science (LNCS). 182-191.
  • Fiala, Jiri; Golovach, Petr; Kratochvil, Jan. 2008. Distance constrained labeling of trees. Lecture Notes in Computer Science (LNCS). 125-135.
  • Fiala, Jiri; Golovach, Petr; Kratochvil, Jan. 2008. Computational complexity of the distance constrained labeling problem for trees. Lecture Notes in Computer Science (LNCS). 294-305.
  • Fiala, Jiri; Golovach, Petr. 2008. Complexity of the packing coloring problem for trees. Lecture Notes in Computer Science (LNCS). 134-145.
  • Dragan, Feodor; Fomin, Fedor; Golovach, Petr. 2008. A PTAS for the sparsest spanners problem on apex-minor-free graphs. Lecture Notes in Computer Science (LNCS). 290-298.
  • Golovach, Petr; Kratochvil, Jan. 2007. Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs. Lecture Notes in Computer Science (LNCS). 1-11.
  • Golovach, Petr; Fomin, Fedor; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2007. Branch and Recharge: Exact Algorithms for Generalized Domination. Lecture Notes in Computer Science (LNCS). 507-518.
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Woeginger, Gerhard J. 2007. Backbone colorings for graphs: Tree and path backbones. Journal of Graph Theory. 137-152.
Academic chapter/article/Conference paper
  • Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr. 2013. Preventing unraveling in social networks gets harder.
  • Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr. 2013. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs.
Abstract
  • Cochefert, Manfred; Couturier, Jean-francois; Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël. 2013. Sparse Square Roots. Lecture Notes in Computer Science (LNCS). 177-188.
  • Belmonte, Rémy; Golovach, Petr; van 't Hof, Pim; Paulusma, Daniël. 2013. Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. Lecture Notes in Computer Science (LNCS). 16-27.
  • Fomin, Fedor; Golovach, Petr; Korhonen, Janne. 2013. On the Parameterized Complexity of Cutting a Few Vertices from a Graph. Lecture Notes in Computer Science (LNCS). 421-432.
  • Fomin, Fedor; Golovach, Petr. 2013. Long Circuits and Large Euler Subgraphs. Lecture Notes in Computer Science (LNCS). 493-504.
  • Golovach, Petr; Paulusma, Daniël. 2013. List Coloring in the Absence of Two Subgraphs. Lecture Notes in Computer Science (LNCS). 288-299.
  • Broersma, Hajo; Fiala, Jiri; Golovach, Petr; Kaiser, Tomas; Paulusma, Daniël; Proskurowski, Andrzej. 2013. Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Lecture Notes in Computer Science (LNCS). 127-138.
  • Golovach, Petr; Paulusma, Daniël; Stewart, Iain. 2013. Graph Editing to a Fixed Target. Lecture Notes in Computer Science (LNCS). 192-205.
  • Dabrowski, K.; Golovach, Petr; Paulusma, Daniël. 2013. Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. Lecture Notes in Computer Science (LNCS). 201-212.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash. 2013. Cliques and Clubs. Lecture Notes in Computer Science (LNCS). 276-287.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve. 2013. An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. Lecture Notes in Computer Science (LNCS). 285-296.

More information in national current research information system (CRIStin)