Petr Golovach's picture
Petr
Golovach
Researcher
Visit Address: 
HIB - Thormøhlensgt. 55
5020 Bergen
Postal Address: 
Postboks 7803
5020 Bergen
Phone: 
+47 55 58 43 85
Download vCard
Journal articles
  • 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. 69: 501-521. doi: 10.1007/s00453-013-9748-5
  • Dabrowski, Konrad K.; Golovach, Petr; Paulusma, Daniël. 2014. Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science. 522: 34-43. doi: 10.1016/j.tcs.2013.12.004
  • Fomin, Fedor; Golovach, Petr. 2014. Long circuits and large euler subgraphs. SIAM Journal on Discrete Mathematics. 28: 878-892. doi: 10.1137/130936816
  • Fomin, Fedor; Golovach, Petr. 2014. Parameterized complexity of connected even/odd subgraph problems. Journal of computer and system sciences (Print). 80: 157-179. doi: 10.1016/j.jcss.2013.07.002
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash. 2014. Finding clubs in graph classes. Discrete Applied Mathematics. 174: 57-65. doi: 10.1016/j.dam.2014.04.016
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; SaeiDinvar, Reza. 2014. Subset feedback vertex sets in chordal graphs. Journal of Discrete Algorithms. 26: 7-15. doi: 10.1016/j.jda.2013.09.005
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve. 2014. An incremental polynomial time Algorithm to enumerate all minimal edge dominating sets. Algorithmica. Published 2014-04-08. doi: 10.1007/s00453-014-9875-7
  • Golovach, Petr; Paulusma, Daniel. 2014. List coloring in the absence of two subgraphs. Discrete Applied Mathematics. 166: 123-130. doi: 10.1016/j.dam.2013.10.010
  • Golovach, Petr; Paulusma, Daniël; Song, Jian. 2014. Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics. 167: 107-120. doi: 10.1016/j.dam.2013.12.008
  • 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. 8246: 16-27.
  • 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. 8165: 127-138.
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Paulusma, Daniël. 2013. Three complexity results on coloring Pk-free graphs. European journal of combinatorics (Print). 34: 609-619. doi: 10.1016/j.ejc.2011.12.008
  • Broersma, Hajo; Golovach, Petr; Patel, Viresh. 2013. Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Theoretical Computer Science. 485: 69-84. doi: 10.1016/j.tcs.2013.03.008
  • Cochefert, Manfred; Couturier, Jean-francois; Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël. 2013. Sparse Square Roots. Lecture Notes in Computer Science. 8165: 177-188.
  • Dabrowski, K.; Golovach, Petr; Paulusma, Daniël. 2013. Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. Lecture Notes in Computer Science. 8165: 201-212.
  • Fomin, Fedor; Golovach, Petr. 2013. Long Circuits and Large Euler Subgraphs. Lecture Notes in Computer Science. 8125: 493-504.
  • Fomin, Fedor; Golovach, Petr; Korhonen, Janne. 2013. On the Parameterized Complexity of Cutting a Few Vertices from a Graph. Lecture Notes in Computer Science. 8087: 421-432.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash. 2013. Cliques and Clubs. Lecture Notes in Computer Science. 7878: 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. 7965: 285-296.
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Manne, Fredrik; Paulusma, Daniël; Pilipczuk, Michal Pawel. 2013. Modifying a Graph Using Vertex Elimination. Algorithmica. doi: 10.1007/s00453-013-9848-2
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Paulusma, Daniel. 2013. Choosability on H-free graphs. Information Processing Letters. 113: 107-110. doi: 10.1016/j.ipl.2012.12.003
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniël. 2013. Detecting induced minors in AT-free graphs. Theoretical Computer Science. 482: 20-32. doi: 10.1016/j.tcs.2013.02.029
  • Golovach, Petr; Paulusma, Daniël. 2013. List Coloring in the Absence of Two Subgraphs. Lecture Notes in Computer Science. 7878: 288-299.
  • Golovach, Petr; Paulusma, Daniël; Stewart, Iain. 2013. Graph Editing to a Fixed Target. Lecture Notes in Computer Science. 8288: 192-205.
  • Golovach, Petr; van 't Hof, Pim; Paulusma, Daniël. 2013. Obtaining planarity by contracting few edges. Theoretical Computer Science. 476: 38-46. doi: 10.1016/j.tcs.2012.12.041
  • Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan. 2012. Parameterized complexity of the spanning tree congestion problem. Algorithmica. 64: 85-111. doi: 10.1007/s00453-011-9565-7
  • 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. 7256: 350-361.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel. 2012. Cops and robber game without recharging. Theory of Computing Systems. 50: 611-620. doi: 10.1007/s00224-011-9360-5
  • Fomin, Fedor; Golovach, Petr; Nederlof, Jesper; Pilipczuk, Michal Pawel. 2012. Minimizing Rosenthal potential in multicast games. Lecture Notes in Computer Science.
  • Fomin, Fedor; Golovach, Petr; Pralat, Pawel. 2012. Cops and robber with constraints. SIAM Journal on Discrete Mathematics. 26: 571-590. doi: 10.1137/110837759
  • 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. 7535: 85-96. doi: 10.1007/978-3-642-33293-7_10
  • Golovach, Petr; Heggernes, Pinar; Mihai, Rodica. 2012. Edge search number of cographs. Discrete Applied Mathematics. 160: 734-743. doi: 10.1016/j.dam.2011.04.020
  • 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. 7551: 320-331. doi: 10.1007/978-3-642-34611-8_32
  • Golovach, Petr; Kratsch, Dieter; Paulusma, Daniel. 2012. Detecting Induced Minors in AT-Free Graphs. Lecture Notes in Computer Science. 7676: 495-505.
  • Golovach, Petr; Paulusma, Daniel; Jian, Song. 2012. Closing Complexity Gaps for Coloring Problems on H-Free Graphs. Lecture Notes in Computer Science. 7676: 14-23.
  • Golovach, Petr; Paulusma, Daniel; Ries, Bernard. 2012. Coloring Graphs Characterized by a Forbidden Subgraph. Lecture Notes in Computer Science. 7664: 443-454.
  • Golovach, Petr; van 't Hof, Pim; Paulusma, Daniel. 2012. Obtaining planarity by contracting few edges. Lecture Notes in Computer Science. 7464: 455-466.
  • Dragan, Feodor F.; Fomin, Fedor; Golovach, Petr. 2011. Approximation of minimum weight spanners for sparse graphs. Theoretical Computer Science. 412: 846-852. doi: 10.1016/j.tcs.2010.11.034
  • Dragan, Feodor F.; Fomin, Fedor; Golovach, Petr. 2011. Spanners in sparse graphs. Journal of computer and system sciences (Print). 77: 1108-1119. doi: 10.1016/j.jcss.2010.10.002
  • Fomin, Fedor; Golovach, Petr; Hall, Alex; Mihalák, Matúš; Vicari, Elias; Widmayer, Peter. 2011. How to Guard a Graph? Algorithmica. 61: 839-856. doi: 10.1007/s00453-009-9382-4
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2011. Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica. 61: 252-273. doi: 10.1007/s00453-010-9418-9
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel. 2011. Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 412: 6484-6497. doi: 10.1016/j.tcs.2011.08.024
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2011. Contraction obstructions for treewidth. Journal of combinatorial theory. Series B (Print). 101: 302-314. doi: 10.1016/j.jctb.2011.02.008
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2011. Approximating width parameters of hypergraphs with excluded minors. SIAM Journal on Discrete Mathematics. 25: 1331-1348. doi: 10.1137/080743226
  • Fomin, Fedor; Golovach, Petr; van Leeuwen, Erik Jan. 2011. Spanners of bounded degree graphs. Information Processing Letters. 111: 142-144. doi: 10.1016/j.ipl.2010.10.021
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket. 2011. Bandwidth on AT-free graphs. Theoretical Computer Science. 412: 7001-7008. doi: 10.1016/j.tcs.2011.09.011
  • Fiala, Jiří; Golovach, Petr. 2010. Complexity of the packing coloring problem for trees. Discrete Applied Mathematics. 158: 771-778. doi: 10.1016/j.dam.2008.09.001
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Nisse, Nicolas; Suchan, Karol. 2010. Pursuing a fast robber on a graph. Theoretical Computer Science. 411: 1167-1181. doi: 10.1016/j.tcs.2009.12.010
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2010. Intractability of clique-width parameterizations. SIAM journal on computing (Print). 39: 1941-1956. doi: 10.1137/080742270
  • Bonato, Anthony; Golovach, Petr; Hahn, Gena; Kratochvil, Jan. 2009. The capture time of a graph. Discrete Mathematics. 309: 5588-5595. doi: 10.1016/j.disc.2008.04.004
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Paulusma, Daniel. 2009. Three Complexity Results on Coloring Pk-Free Graphs. Lecture Notes in Computer Science. 5874: 95-104. doi: 10.1007/978-3-642-10217-2_12
  • Fiala, Jiří; Golovach, Petr; Kratochvil, Jan. 2009. Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. Lecture Notes in Computer Science. 5532: 221-230. doi: 10.1007/978-3-642-02017-9_25
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2009. Sort and Search: Exact algorithms for generalized domination. Information Processing Letters. 109: 795-798. doi: 10.1016/j.ipl.2009.03.023
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios. 2009. Approximating Acyclicity Parameters of Sparse Hypergraphs. Leibniz International Proceedings in Informatics. 3: 445-456. doi: 10.4230/LIPIcs.STACS.2009.1803
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios. 2009. Contraction Bidimensionality: The Accurate Picture. Lecture Notes in Computer Science. 5757: 706-717. doi: http://dx.doi.org/10.1007/978-3-642-04128-0
  • Golovach, Petr; Heggernes, Pinar. 2009. Choosability of P5-free graphs. Lecture Notes in Computer Science. 5734: 382-391. doi: 10.1007/978-3-642-03816-7_33
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket. 2009. Bandwidth on AT-Free Graphs. Lecture Notes in Computer Science. 5878: 573-582. doi: 10.1007/978-3-642-10631-6_59
  • Golovach, Petr; Kaminski, M.; Paulusma, Daniel; Thilikos, Dimitrios M. 2009. Induced Packing of Odd Cycles in a Planar Graph. Lecture Notes in Computer Science. 5878: 514-523. doi: 10.1007/978-3-642-10631-6_53
  • Golovach, Petr; Kratochvil, Jan; Suchy, Ondra. 2009. Parameterized Complexity of Generalized Domination Problems. Lecture Notes in Computer Science. 5911: 133-142. doi: 10.1007/978-3-642-11409-0_12
  • Golovach, Petr; Thilikos, Dimitrios M. 2009. Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms. Lecture Notes in Computer Science. 5917: 210-221. doi: 10.1007/978-3-642-11269-0_17
  • Dragan, Feodor; Fomin, Fedor; Golovach, Petr. 2008. A PTAS for the sparsest spanners problem on apex-minor-free graphs. Lecture Notes in Computer Science. 5162: 290-298.
  • Dragan, Feodor; Fomin, Fedor; Golovach, Petr. 2008. Spanners in sparse graphs. Lecture Notes in Computer Science. 5125: 597-608.
  • Fiala, Jiri; Golovach, Petr. 2008. Complexity of the packing coloring problem for trees. Lecture Notes in Computer Science. 5344: 134-145.
  • Fiala, Jiri; Golovach, Petr; Kratochvil, Jan. 2008. Computational complexity of the distance constrained labeling problem for trees. Lecture Notes in Computer Science. 5125: 294-305.
  • Fiala, Jiri; Golovach, Petr; Kratochvil, Jan. 2008. Distance constrained labeling of trees. Lecture Notes in Computer Science. 4978: 125-135.
  • Fomin, Fedor; Golovach, Petr; Hall, Alex; Mihalak, Matus; Vicari, Elias; Widmayer, Peter. 2008. How to guard a graph? Lecture Notes in Computer Science. 5369: 318-239.
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan. 2008. On tractability cops and robbers game. IFIP International Federation for Information Processing. 237: 171-185.
  • Golovach, Petr; Kratochvil, Jan. 2008. Generalized domination in degenerate graphs: a complete dichotomy of computational complexity. Lecture Notes in Computer Science. 4978: 182-191.
  • Golovach, Petr; Villanger, Yngve. 2008. Parameterized complexity for domination problems on degenerate graphs. Lecture Notes in Computer Science. 5344: 195-205.
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Woeginger, Gerhard J. 2007. Backbone colorings for graphs: Tree and path backbones. Journal of Graph Theory. 55: 137-152. doi: 10.1002/jgt.20228
  • Golovach, Petr; Fomin, Fedor; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2007. Branch and Recharge: Exact Algorithms for Generalized Domination. Lecture Notes in Computer Science. 4619: 507-518.
  • Golovach, Petr; Kratochvil, Jan. 2007. Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs. Lecture Notes in Computer Science. 4769: 1-11.
Book sections
  • Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr. 2013. Preventing unraveling in social networks gets harder. Extended abstract. In:
    • desJardins, Marie; Littman, Michael. 2013. Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. AAAI Press. ISBN: 978-1-57735-615-8.
  • Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr. 2013. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. Extended abstract, pages 79-90. In:
    • Seth, Anil; Vishnoi, Nisheeth. 2013. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India. 539 pages. ISBN: 978-3-939897-64-4.

More information in national current research information system (CRIStin)