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
  • 2020. Parameterized Aspects of Strong Subgraph Closure. Algorithmica.
  • 2019. Surjective H-colouring: New hardness results. Computability - The Journal of the Assosiation. 27-42.
  • 2019. Spanning circuits in regular matroids. ACM Transactions on Algorithms (TALG).
  • 2019. Refined Complexity of PCA with Outliers. Proceedings of Machine Learning Research (PMLR). 5818-5826.
  • 2019. Parameterized k-Clustering: Tractability Island. Leibniz International Proceedings in Informatics. 14:1-14:15.
  • 2019. On the parameterized complexity of graph modification to first-order logic properties. Theory of Computing Systems. 251-271.
  • 2019. Modification to planarity is fixed parameter tractable. Leibniz International Proceedings in Informatics. 28:1-28:17.
  • 2019. Kernelization of graph hamiltonicity: Proper H-graphs. Lecture Notes in Computer Science (LNCS). 296-310.
  • 2019. Going Far From Degeneracy. Leibniz International Proceedings in Informatics. 47:1-47:14.
  • 2019. Enumeration of Minimal Connected Dominating Sets for Chordal Graphs. Discrete Applied Mathematics.
  • 2019. Enumeration and maximum number of minimal dominating sets for chordal graphs. Theoretical Computer Science. 41-52.
  • 2019. Enumeration and maximum number of maximal irredundant sets for chordal graphs. Discrete Applied Mathematics. 69-85.
  • 2019. Editing to connected F-degree graph. SIAM Journal on Discrete Mathematics. 795-836.
  • 2019. Cyclability in Graph Classes. Leibniz International Proceedings in Informatics. 16:1-16:13.
  • 2019. Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. Leibniz International Proceedings in Informatics. 59:1-59:13.
  • 2019. Clustering to Given Connectivities. Leibniz International Proceedings in Informatics. 18:1-18:17.
  • 2019. Approximation Schemes for Low-rank Binary Matrix Approximation Problems. ACM Transactions on Algorithms (TALG). 12:1-12:39.
  • 2019. Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2. Algorithmica. 2795-2828.
  • 2018. Structured connectivity augmentation. SIAM Journal on Discrete Mathematics. 2612-2635.
  • 2018. Partial Complementation of Graphs. Leibniz International Proceedings in Informatics. 21:1-21:13.
  • 2018. Parameterized low-rank binary matrix approximation. Leibniz International Proceedings in Informatics. 1-16.
  • 2018. Parameterized Aspects of Strong Subgraph Closure. Leibniz International Proceedings in Informatics. 23:1-23:13.
  • 2018. Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Algorithmica. 714-741.
  • 2018. On the tractability of optimization problems on H-graphs. Leibniz International Proceedings in Informatics. 1-14.
  • 2018. Finding connected secluded subgraphs. Leibniz International Proceedings in Informatics. 1-13.
  • 2018. Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs. European journal of combinatorics (Print). 132-147.
  • 2018. Covering Vectors by Spaces: Regular Matroids. SIAM Journal on Discrete Mathematics. 2512-2565.
  • 2018. Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics. 93-101.
  • 2018. Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 262-273.
  • 2018. Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG). 27 pages.
  • 2017. The parameterized complexity of graph cyclability. SIAM Journal on Discrete Mathematics. 511-541.
  • 2017. Surjective H-colouring: New hardness results. Lecture Notes in Computer Science (LNCS). 270-281.
  • 2017. Structured Connectivity Augmentation. Leibniz International Proceedings in Informatics.
  • 2017. Spanning Circuits in Regular Matroids. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1433-1441.
  • 2017. Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Algorithmica. 714-741.
  • 2017. On recognition of threshold tolerance graphs and their complements. Discrete Applied Mathematics. 171-180.
  • 2017. Minimal dominating sets in interval graphs and trees. Discrete Applied Mathematics. 162-170.
  • 2017. Metric Dimension of Bounded Tree-length Graphs. SIAM Journal on Discrete Mathematics. 1217-1243.
  • 2017. Graph editing to a given degree sequence. Theoretical Computer Science. 1-12.
  • 2017. Graph editing to a fixed target. Discrete Applied Mathematics. 181-190.
  • 2017. Finding Cactus Roots in Polynomial Time. Theory of Computing Systems. 1-18.
  • 2017. Enumeration of maximal irredundant sets for claw-free graphs. Lecture Notes in Computer Science (LNCS). 297-309.
  • 2017. Enumeration and maximum number of maximal irredundant sets for chordal graphs. Lecture Notes in Computer Science (LNCS). 289-302.
  • 2017. Editing to a planar graph of given degrees. Journal of computer and system sciences (Print). 168-182.
  • 2017. Editing to a connected graph of given degrees. Information and Computation. 131-147.
  • 2017. Covering vectors by spaces: Regular matroids. Leibniz International Proceedings in Informatics. 1-15.
  • 2017. Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Lecture Notes in Computer Science (LNCS). 275-288.
  • 2017. A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science. 36-47.
  • 2017. A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory. 331-363.
  • 2016. Squares of low clique number. Electronic Notes in Discrete Mathematics. 195-198.
  • 2016. Parameterized complexity of the anchored k-core problem for directed graphs. Information and Computation. 11-22.
  • 2016. Parameterized complexity of secluded connectivity problems. Theory of Computing Systems. 1-25.
  • 2016. Parameterized algorithms for finding square roots. Algorithmica. 602-629.
  • 2016. Parameterized Complexity of Superstring Problems. Algorithmica. 1-16.
  • 2016. Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science. 70-83.
  • 2016. How to hunt an invisible rabbit on a graph. European journal of combinatorics (Print). 12-26.
  • 2016. Graph editing to a given degree sequence. Lecture Notes in Computer Science (LNCS). 177-191.
  • 2016. Finding cactus roots in polynomial time. Lecture Notes in Computer Science (LNCS). 361-372.
  • 2016. Enumeration and maximum number of minimal connected vertex covers in graphs. Lecture Notes in Computer Science (LNCS). 235-247.
  • 2016. Enumerating minimal dominating sets in chordal bipartite graphs. Discrete Applied Mathematics. 30-36.
  • 2016. Enumerating minimal connected dominating sets in graphs of bounded chordality. Theoretical Computer Science. 63-75.
  • 2016. Editing to connected f-degree graph. Leibniz International Proceedings in Informatics. 1-15.
  • 2016. Editing to Eulerian graphs. Journal of computer and system sciences (Print). 213-228.
  • 2016. A linear kernel for finding square roots of almost planar graphs. Leibniz International Proceedings in Informatics. 4.1-4.14.
  • 2015. Variants of plane diameter completion. Leibniz International Proceedings in Informatics. 30-42.
  • 2015. Parameterized complexity of superstring problems. Lecture Notes in Computer Science (LNCS). 89-99.
  • 2015. Parameterized complexity of secluded connectivity problems. Leibniz International Proceedings in Informatics. 408-419.
  • 2015. Output-polynomial enumeration on graphs of bounded (local) linear mim-width. Lecture Notes in Computer Science (LNCS). 248-258.
  • 2015. Modifying a graph using vertex elimination. Algorithmica. 99-125.
  • 2015. Minimizing Rosenthal potential in multicast games. Theory of Computing Systems. 81-96.
  • 2015. Metric dimension of bounded width graphs. Lecture Notes in Computer Science (LNCS). 115-126.
  • 2015. List coloring in the absence of a linear forest. Algorithmica. 21-35.
  • 2015. Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs665. Journal of Graph Theory. 282-299.
  • 2015. Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics. 348-375.
  • 2015. Hadwiger number of graphs with small chordality. Lecture Notes in Computer Science (LNCS). 201-213.
  • 2015. Hadwiger number of graphs with small chordality. SIAM Journal on Discrete Mathematics. 1427-1451.
  • 2015. Enumerating minimal connected dominating sets in graphs of bounded chordality. Leibniz International Proceedings in Informatics. 307-318.
  • 2015. Editing to a planar graph of given degrees. Lecture Notes in Computer Science (LNCS). 143-156.
  • 2015. Editing to a Graph of Given Degrees. Theoretical Computer Science. 72-84.
  • 2015. Editing to a Connected Graph of Given Degrees. Lecture Notes in Computer Science (LNCS). 324-335.
  • 2015. Coloring graphs characterized by a forbidden subgraph. Discrete Applied Mathematics. 101-110.
  • 2015. An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Algorithmica. 836-859.
  • 2014. The parameterized complexity of graph cyclability. Lecture Notes in Computer Science (LNCS). 492-504.
  • 2014. Subset feedback vertex sets in chordal graphs. Journal of Discrete Algorithms. 7-15.
  • 2014. Solutions for the stable roommates problem with payments. Theoretical Computer Science. 53-61.
  • 2014. Recognizing Threshold Tolerance Graphs in O(n^2) Time. Lecture Notes in Computer Science (LNCS). 214-224.
  • 2014. Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica. 473-497.
  • 2014. Parameterized complexity of connected even/odd subgraph problems. Journal of computer and system sciences (Print). 157-179.
  • 2014. Parameterized algorithms to preserve connectivity. Lecture Notes in Computer Science (LNCS). 800-811.
  • 2014. On Recognition of Threshold Tolerance Graphs and their Complements. Lecture Notes in Computer Science (LNCS). 214-224.
  • 2014. Long circuits and large euler subgraphs. SIAM Journal on Discrete Mathematics. 878-892.
  • 2014. List coloring in the absence of two subgraphs. Discrete Applied Mathematics. 123-130.
  • 2014. Lift-contractions. European journal of combinatorics (Print). 286-296.
  • 2014. Induced disjoint paths in circular-arc graphs in linear time. Lecture Notes in Computer Science (LNCS). 225-237.
  • 2014. Finding clubs in graph classes. Discrete Applied Mathematics. 57-65.
  • 2014. Editing to a Graph of Given Degrees. Lecture Notes in Computer Science (LNCS). 196-207.
  • 2014. Editing to Eulerian graphs. Leibniz International Proceedings in Informatics. 97-108.
  • 2014. Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica. 501-521.
  • 2014. Connecting vertices by independent trees. Leibniz International Proceedings in Informatics. 73-84.
  • 2014. Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science. 34-43.
  • 2014. Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics. 107-120.
  • 2014. Closing complexity gaps for coloring problems on H-free graphs. Information and Computation. 204-214.
  • 2014. An incremental polynomial time Algorithm to enumerate all minimal edge dominating sets. Algorithmica. 836-859.
  • 2014. An exact algorithm for Subset Feedback Vertex Set on chordal graphs. Journal of Discrete Algorithms. 7-15.
  • 2014. Almost optimal lower bounds for problems parameterized by clique-width. SIAM journal on computing (Print). 1541-1563.
  • 2013. Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Theoretical Computer Science. 69-84.
  • 2013. Three complexity results on coloring Pk-free graphs. European journal of combinatorics (Print). 609-619.
  • 2013. Obtaining planarity by contracting few edges. Theoretical Computer Science. 38-46.
  • 2013. Modifying a Graph Using Vertex Elimination. Algorithmica.
  • 2013. Detecting induced minors in AT-free graphs. Theoretical Computer Science. 20-32.
  • 2013. Choosability on H-free graphs. Information Processing Letters. 107-110.
  • 2012. k-Gap Interval Graphs. Lecture Notes in Computer Science (LNCS). 350-361.
  • 2012. Parameterized complexity of the spanning tree congestion problem. Algorithmica. 85-111.
  • 2012. Obtaining planarity by contracting few edges. Lecture Notes in Computer Science (LNCS). 455-466.
  • 2012. Minimizing Rosenthal potential in multicast games. Lecture Notes in Computer Science (LNCS).
  • 2012. How to Eliminate a Graph. Lecture Notes in Computer Science (LNCS). 320-331.
  • 2012. Edge search number of cographs. Discrete Applied Mathematics. 734-743.
  • 2012. Detecting Induced Minors in AT-Free Graphs. Lecture Notes in Computer Science (LNCS). 495-505.
  • 2012. Cops and robber with constraints. SIAM Journal on Discrete Mathematics. 571-590.
  • 2012. Cops and robber game without recharging. Theory of Computing Systems. 611-620.
  • 2012. Coloring Graphs Characterized by a Forbidden Subgraph. Lecture Notes in Computer Science (LNCS). 443-454.
  • 2012. Closing Complexity Gaps for Coloring Problems on H-Free Graphs. Lecture Notes in Computer Science (LNCS). 14-23.
  • 2012. An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs. Lecture Notes in Computer Science (LNCS). 85-96.
  • 2011. Spanners of bounded degree graphs. Information Processing Letters. 142-144.
  • 2011. Spanners in sparse graphs. Journal of computer and system sciences (Print). 1108-1119.
  • 2011. How to Guard a Graph? Algorithmica. 839-856.
  • 2011. Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 6484-6497.
  • 2011. Contraction obstructions for treewidth. Journal of combinatorial theory. Series B (Print). 302-314.
  • 2011. Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica. 252-273.
  • 2011. Bandwidth on AT-free graphs. Theoretical Computer Science. 7001-7008.
  • 2011. Approximation of minimum weight spanners for sparse graphs. Theoretical Computer Science. 846-852.
  • 2011. Approximating width parameters of hypergraphs with excluded minors. SIAM Journal on Discrete Mathematics. 1331-1348.
  • 2010. Pursuing a fast robber on a graph. Theoretical Computer Science. 1167-1181.
  • 2010. Intractability of clique-width parameterizations. SIAM journal on computing (Print). 1941-1956.
  • 2010. Complexity of the packing coloring problem for trees. Discrete Applied Mathematics. 771-778.
  • 2009. Three Complexity Results on Coloring Pk-Free Graphs. Lecture Notes in Computer Science (LNCS). 95-104.
  • 2009. The capture time of a graph. Discrete Mathematics. 5588-5595.
  • 2009. Sort and Search: Exact algorithms for generalized domination. Information Processing Letters. 795-798.
  • 2009. Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms. Lecture Notes in Computer Science (LNCS). 210-221.
  • 2009. Parameterized Complexity of Generalized Domination Problems. Lecture Notes in Computer Science (LNCS). 133-142.
  • 2009. Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. Lecture Notes in Computer Science (LNCS). 221-230.
  • 2009. Induced Packing of Odd Cycles in a Planar Graph. Lecture Notes in Computer Science (LNCS). 514-523.
  • 2009. Contraction Bidimensionality: The Accurate Picture. Lecture Notes in Computer Science (LNCS). 706-717.
  • 2009. Choosability of P5-free graphs. Lecture Notes in Computer Science (LNCS). 382-391.
  • 2009. Bandwidth on AT-Free Graphs. Lecture Notes in Computer Science (LNCS). 573-582.
  • 2009. Approximating Acyclicity Parameters of Sparse Hypergraphs. Leibniz International Proceedings in Informatics. 445-456.
  • 2008. Spanners in sparse graphs. Lecture Notes in Computer Science (LNCS). 597-608.
  • 2008. Parameterized complexity for domination problems on degenerate graphs. Lecture Notes in Computer Science (LNCS). 195-205.
  • 2008. On tractability cops and robbers game. IFIP International Federation for Information Processing. 171-185.
  • 2008. How to guard a graph? Lecture Notes in Computer Science (LNCS). 318-239.
  • 2008. Generalized domination in degenerate graphs: a complete dichotomy of computational complexity. Lecture Notes in Computer Science (LNCS). 182-191.
  • 2008. Distance constrained labeling of trees. Lecture Notes in Computer Science (LNCS). 125-135.
  • 2008. Computational complexity of the distance constrained labeling problem for trees. Lecture Notes in Computer Science (LNCS). 294-305.
  • 2008. Complexity of the packing coloring problem for trees. Lecture Notes in Computer Science (LNCS). 134-145.
  • 2008. A PTAS for the sparsest spanners problem on apex-minor-free graphs. Lecture Notes in Computer Science (LNCS). 290-298.
  • 2007. Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs. Lecture Notes in Computer Science (LNCS). 1-11.
  • 2007. Branch and Recharge: Exact Algorithms for Generalized Domination. Lecture Notes in Computer Science (LNCS). 507-518.
  • 2007. Backbone colorings for graphs: Tree and path backbones. Journal of Graph Theory. 137-152.
Academic chapter/article/Conference paper
  • 2013. Preventing unraveling in social networks gets harder.
  • 2013. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. 12 pages.
Abstract
  • 2013. Sparse Square Roots. Lecture Notes in Computer Science (LNCS). 177-188.
  • 2013. Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. Lecture Notes in Computer Science (LNCS). 16-27.
  • 2013. On the Parameterized Complexity of Cutting a Few Vertices from a Graph. Lecture Notes in Computer Science (LNCS). 421-432.
  • 2013. Long Circuits and Large Euler Subgraphs. Lecture Notes in Computer Science (LNCS). 493-504.
  • 2013. List Coloring in the Absence of Two Subgraphs. Lecture Notes in Computer Science (LNCS). 288-299.
  • 2013. Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Lecture Notes in Computer Science (LNCS). 127-138.
  • 2013. Graph Editing to a Fixed Target. Lecture Notes in Computer Science (LNCS). 192-205.
  • 2013. Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. Lecture Notes in Computer Science (LNCS). 201-212.
  • 2013. Cliques and Clubs. Lecture Notes in Computer Science (LNCS). 276-287.
  • 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)