Petr Golovach

E-mailpetr.golovach@uib.no
Phone+47 55 58 43 85
Visitor Address
HIB - Thormøhlens gate 55

5006 Bergen

Room
307P2
Postal Address
Postboks 7803

5020 Bergen

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).

Show author(s) (2023). Two-sets cut-uncut on planar graphs. arXiv.org.
Show author(s) (2023). Parameterized complexity of categorical clustering with size constraints. Journal of computer and system sciences. 171-194.
Show author(s) (2023). Lossy Kernelization of Same-Size Clustering. Theory of Computing Systems. 785-824.
Show author(s) (2023). How to find a good explanation for clustering? Artificial Intelligence.
Show author(s) (2023). Diverse collections in matroids and graphs. Mathematical programming.
Show author(s) (2023). Detours in directed graphs. Journal of computer and system sciences. 66-86.
Show author(s) (2023). Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs. Information and Computation.
Show author(s) (2023). An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL. ACM Transactions on Computation Theory. 1-29.
Show author(s) (2023). A survey of parameterized algorithms and the complexity of edge modification. Computer Science Review. 100556-100556.

Show author(s) (2022). Present-biased optimization. Mathematical Social Sciences. 56-67.
Show author(s) (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science. 37-52.
Show author(s) (2022). Parameterized Complexity of Elimination Distance to First-Order Logic Properties. ACM Transactions on Computational Logic. 1-35.
Show author(s) (2022). Lossy Kernelization of Same-Size Clustering. Lecture Notes in Computer Science (LNCS). 96-114.
Show author(s) (2022). Longest Cycle Above Erdös-Gallai Bound. Leibniz International Proceedings in Informatics. 1-15.
Show author(s) (2022). Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms. Leibniz International Proceedings in Informatics. 1-4.
Show author(s) (2022). Induced Disjoint Paths in AT-free graphs. Journal of computer and system sciences. 170-191.
Show author(s) (2022). How to Find a Good Explanation for Clustering? Proceedings of the AAAI Conference on Artificial Intelligence. 3904-3912.
Show author(s) (2022). Graph Square Roots of Small Distance from Degree One Graphs. Theory of Computing Systems. 821-846.
Show author(s) (2022). FPT Approximation for Fair Minimum-Load Clustering. Leibniz International Proceedings in Informatics. 1-14.
Show author(s) (2022). Exact Exponential Algorithms for Clustering Problems. Leibniz International Proceedings in Informatics. 1-14.
Show author(s) (2022). Detours in Directed Graphs. Leibniz International Proceedings in Informatics. 1-6.
Show author(s) (2022). Cyclability in graph classes. Discrete Applied Mathematics. 147-178.
Show author(s) (2022). Algorithmic Extensions of Dirac's Theorem. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 406-416.
Show author(s) (2022). Acyclic, star, and injective colouring: bounding the diameter<sup>∗</sup>. The Electronic Journal of Combinatorics. 29 pages.
Show author(s) (2022). (Re)packing Equal Disks into Rectangle. Leibniz International Proceedings in Informatics. 1-17.

Show author(s) (2021). Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. Algorithmica. 2170-2214.
Show author(s) (2021). Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. Journal of computer and system sciences. 76-102.
Show author(s) (2021). Present-Biased Optimization. Proceedings of the AAAI Conference on Artificial Intelligence. 5415-5422.
Show author(s) (2021). Partitioning H-Free Graphs of Bounded Diameter. Leibniz International Proceedings in Informatics. 21:1-21:14.
Show author(s) (2021). Parameterized k-Clustering: Tractability island. Journal of computer and system sciences. 50-74.
Show author(s) (2021). Parameterized Complexity of Feature Selection for Categorical Data Clustering. Leibniz International Proceedings in Informatics. 14:1-14:14.
Show author(s) (2021). Parameterized Complexity of Elimination Distance to First-Order Logic Properties. Logic in Computer Science. 1-13.
Show author(s) (2021). Parameterized Complexity of Directed Spanner Problems. Algorithmica. 17 pages.
Show author(s) (2021). Parameterized Complexity of Categorical Clustering with Size Constraints. Lecture Notes in Computer Science (LNCS). 385-398.
Show author(s) (2021). Kernelization of Whitney Switches. SIAM Journal on Discrete Mathematics. 1298-1336.
Show author(s) (2021). Kernelization of Graph Hamiltonicity: Proper H-Graphs. SIAM Journal on Discrete Mathematics. 840-892.
Show author(s) (2021). ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space. Leibniz International Proceedings in Informatics. 21:1-21:16.
Show author(s) (2021). EPTAS for k-means Clustering of Affine Subspaces. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 2649-2659.
Show author(s) (2021). Diverse Collections in Matroids and Graphs. Leibniz International Proceedings in Informatics. 31:1-31:14.
Show author(s) (2021). Can Romeo and Juliet Meet? or Rendezvous Games with Adversaries on Graphs. Lecture Notes in Computer Science (LNCS). 308-320.
Show author(s) (2021). Acyclic, Star, and Injective Colouring: Bounding the Diameter. Lecture Notes in Computer Science (LNCS). 336-348.

Show author(s) (2020). Subgraph Complementation. Algorithmica. 1859-1880.
Show author(s) (2020). Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. Leibniz International Proceedings in Informatics. 49:1-49:17.
Show author(s) (2020). Recognizing Proper Tree-Graphs. Leibniz International Proceedings in Informatics. 8:1-8:15.
Show author(s) (2020). Parameterized low-rank binary matrix approximation. Data mining and knowledge discovery. 478-532.
Show author(s) (2020). Parameterized complexity of PCA. Leibniz International Proceedings in Informatics. 1:1-1:5.
Show author(s) (2020). Parameterized Complexity of Directed Spanner Problems. Leibniz International Proceedings in Informatics. 12:1-12:11.
Show author(s) (2020). Parameterized Aspects of Strong Subgraph Closure. Algorithmica. 2006-2038.
Show author(s) (2020). Parameterization Above a Multiplicative Guarantee . Leibniz International Proceedings in Informatics. 39:1-39:13.
Show author(s) (2020). On the Tractability of Optimization Problems on H-Graphs. Algorithmica. 2432-2473.
Show author(s) (2020). On the Complexity of Recovering Incidence Matrices. Leibniz International Proceedings in Informatics. 50:1-50:13.
Show author(s) (2020). Low-Rank Binary Matrix Approximation in Column-Sum Norm. Leibniz International Proceedings in Informatics. 32:1-32:18.
Show author(s) (2020). Kernelization of Whitney Switches. Leibniz International Proceedings in Informatics. 48:1-48:19.
Show author(s) (2020). Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 931-950.
Show author(s) (2020). Graph Square Roots of Small Distance from Degree One Graphs. Lecture Notes in Computer Science (LNCS). 116-128.
Show author(s) (2020). Graph Hamiltonicity Parameterized by Proper Interval Deletion Set. Lecture Notes in Computer Science (LNCS). 104-115.
Show author(s) (2020). Going Far from Degeneracy. SIAM Journal on Discrete Mathematics. 1578-1601.
Show author(s) (2020). Finding connected secluded subgraphs. Journal of computer and system sciences. 101-124.
Show author(s) (2020). Diverse Pairs of Matchings. Leibniz International Proceedings in Informatics. 26:1-26:12.
Show author(s) (2020). An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL. Leibniz International Proceedings in Informatics. 51:1-51:17.

Show author(s) (2019). Surjective H-colouring: New hardness results. Computability - The Journal of the Assosiation. 27-42.
Show author(s) (2019). Spanning circuits in regular matroids. ACM Transactions on Algorithms (TALG).
Show author(s) (2019). Refined Complexity of PCA with Outliers. Proceedings of Machine Learning Research (PMLR). 5818-5826.
Show author(s) (2019). Parameterized k-Clustering: Tractability Island. Leibniz International Proceedings in Informatics. 14:1-14:15.
Show author(s) (2019). On the parameterized complexity of graph modification to first-order logic properties. Theory of Computing Systems. 251-271.
Show author(s) (2019). Modification to planarity is fixed parameter tractable. Leibniz International Proceedings in Informatics. 28:1-28:17.
Show author(s) (2019). Kernelization of graph hamiltonicity: Proper H-graphs. Lecture Notes in Computer Science (LNCS). 296-310.
Show author(s) (2019). Going Far From Degeneracy. Leibniz International Proceedings in Informatics. 47:1-47:14.
Show author(s) (2019). Enumeration of Minimal Connected Dominating Sets for Chordal Graphs. Discrete Applied Mathematics. 3-11.
Show author(s) (2019). Enumeration and maximum number of minimal dominating sets for chordal graphs. Theoretical Computer Science. 41-52.
Show author(s) (2019). Enumeration and maximum number of maximal irredundant sets for chordal graphs. Discrete Applied Mathematics. 69-85.
Show author(s) (2019). Editing to connected F-degree graph. SIAM Journal on Discrete Mathematics. 795-836.
Show author(s) (2019). Cyclability in Graph Classes. Leibniz International Proceedings in Informatics. 16:1-16:13.
Show author(s) (2019). Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. Leibniz International Proceedings in Informatics. 59:1-59:13.
Show author(s) (2019). Clustering to Given Connectivities. Leibniz International Proceedings in Informatics. 18:1-18:17.
Show author(s) (2019). Approximation Schemes for Low-rank Binary Matrix Approximation Problems. ACM Transactions on Algorithms (TALG). 12:1-12:39.
Show author(s) (2019). Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2. Algorithmica. 2795-2828.

Show author(s) (2018). Structured connectivity augmentation. SIAM Journal on Discrete Mathematics. 2612-2635.
Show author(s) (2018). Partial Complementation of Graphs. Leibniz International Proceedings in Informatics. 21:1-21:13.
Show author(s) (2018). Parameterized low-rank binary matrix approximation. Leibniz International Proceedings in Informatics. 1-16.
Show author(s) (2018). Parameterized Aspects of Strong Subgraph Closure. Leibniz International Proceedings in Informatics. 23:1-23:13.
Show author(s) (2018). Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Algorithmica. 714-741.
Show author(s) (2018). On the tractability of optimization problems on H-graphs. Leibniz International Proceedings in Informatics. 1-14.
Show author(s) (2018). Finding connected secluded subgraphs. Leibniz International Proceedings in Informatics. 1-13.
Show author(s) (2018). Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs. European journal of combinatorics (Print). 132-147.
Show author(s) (2018). Covering Vectors by Spaces: Regular Matroids. SIAM Journal on Discrete Mathematics. 2512-2565.
Show author(s) (2018). Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics. 93-101.
Show author(s) (2018). Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 262-273.
Show author(s) (2018). Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG). 27 pages.

Show author(s) (2017). The parameterized complexity of graph cyclability. SIAM Journal on Discrete Mathematics. 511-541.
Show author(s) (2017). Surjective H-colouring: New hardness results. Lecture Notes in Computer Science (LNCS). 270-281.
Show author(s) (2017). Structured Connectivity Augmentation. Leibniz International Proceedings in Informatics.
Show author(s) (2017). Spanning Circuits in Regular Matroids. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1433-1441.
Show author(s) (2017). Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Algorithmica. 714-741.
Show author(s) (2017). On recognition of threshold tolerance graphs and their complements. Discrete Applied Mathematics. 171-180.
Show author(s) (2017). Minimal dominating sets in interval graphs and trees. Discrete Applied Mathematics. 162-170.
Show author(s) (2017). Metric Dimension of Bounded Tree-length Graphs. SIAM Journal on Discrete Mathematics. 1217-1243.
Show author(s) (2017). Graph editing to a given degree sequence. Theoretical Computer Science. 1-12.
Show author(s) (2017). Graph editing to a fixed target. Discrete Applied Mathematics. 181-190.
Show author(s) (2017). Finding Cactus Roots in Polynomial Time. Theory of Computing Systems. 1-18.
Show author(s) (2017). Enumeration of maximal irredundant sets for claw-free graphs. Lecture Notes in Computer Science (LNCS). 297-309.
Show author(s) (2017). Enumeration and maximum number of maximal irredundant sets for chordal graphs. Lecture Notes in Computer Science (LNCS). 289-302.
Show author(s) (2017). Editing to a planar graph of given degrees. Journal of computer and system sciences. 168-182.
Show author(s) (2017). Editing to a connected graph of given degrees. Information and Computation. 131-147.
Show author(s) (2017). Covering vectors by spaces: Regular matroids. Leibniz International Proceedings in Informatics. 1-15.
Show author(s) (2017). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Lecture Notes in Computer Science (LNCS). 275-288.
Show author(s) (2017). A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science. 36-47.
Show author(s) (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory. 331-363.

Show author(s) (2016). Squares of low clique number. Electronic Notes in Discrete Mathematics. 195-198.
Show author(s) (2016). Parameterized complexity of the anchored k-core problem for directed graphs. Information and Computation. 11-22.
Show author(s) (2016). Parameterized complexity of secluded connectivity problems. Theory of Computing Systems. 1-25.
Show author(s) (2016). Parameterized algorithms for finding square roots. Algorithmica. 602-629.
Show author(s) (2016). Parameterized Complexity of Superstring Problems. Algorithmica. 1-16.
Show author(s) (2016). Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science. 70-83.
Show author(s) (2016). How to hunt an invisible rabbit on a graph. European journal of combinatorics (Print). 12-26.
Show author(s) (2016). Graph editing to a given degree sequence. Lecture Notes in Computer Science (LNCS). 177-191.
Show author(s) (2016). Finding cactus roots in polynomial time. Lecture Notes in Computer Science (LNCS). 361-372.
Show author(s) (2016). Enumeration and maximum number of minimal connected vertex covers in graphs. Lecture Notes in Computer Science (LNCS). 235-247.
Show author(s) (2016). Enumerating minimal dominating sets in chordal bipartite graphs. Discrete Applied Mathematics. 30-36.
Show author(s) (2016). Enumerating minimal connected dominating sets in graphs of bounded chordality. Theoretical Computer Science. 63-75.
Show author(s) (2016). Editing to connected f-degree graph. Leibniz International Proceedings in Informatics. 1-15.
Show author(s) (2016). Editing to Eulerian graphs. Journal of computer and system sciences. 213-228.
Show author(s) (2016). A linear kernel for finding square roots of almost planar graphs. Leibniz International Proceedings in Informatics. 4.1-4.14.

Show author(s) (2015). Variants of plane diameter completion. Leibniz International Proceedings in Informatics. 30-42.
Show author(s) (2015). Parameterized complexity of superstring problems. Lecture Notes in Computer Science (LNCS). 89-99.
Show author(s) (2015). Parameterized complexity of secluded connectivity problems. Leibniz International Proceedings in Informatics. 408-419.
Show author(s) (2015). Output-polynomial enumeration on graphs of bounded (local) linear mim-width. Lecture Notes in Computer Science (LNCS). 248-258.
Show author(s) (2015). Modifying a graph using vertex elimination. Algorithmica. 99-125.
Show author(s) (2015). Minimizing Rosenthal potential in multicast games. Theory of Computing Systems. 81-96.
Show author(s) (2015). Metric dimension of bounded width graphs. Lecture Notes in Computer Science (LNCS). 115-126.
Show author(s) (2015). List coloring in the absence of a linear forest. Algorithmica. 21-35.
Show author(s) (2015). Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs665. Journal of Graph Theory. 282-299.
Show author(s) (2015). Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics. 348-375.
Show author(s) (2015). Hadwiger number of graphs with small chordality. Lecture Notes in Computer Science (LNCS). 201-213.
Show author(s) (2015). Hadwiger number of graphs with small chordality. SIAM Journal on Discrete Mathematics. 1427-1451.
Show author(s) (2015). Enumerating minimal connected dominating sets in graphs of bounded chordality. Leibniz International Proceedings in Informatics. 307-318.
Show author(s) (2015). Editing to a planar graph of given degrees. Lecture Notes in Computer Science (LNCS). 143-156.
Show author(s) (2015). Editing to a Graph of Given Degrees. Theoretical Computer Science. 72-84.
Show author(s) (2015). Editing to a Connected Graph of Given Degrees. Lecture Notes in Computer Science (LNCS). 324-335.
Show author(s) (2015). Coloring graphs characterized by a forbidden subgraph. Discrete Applied Mathematics. 101-110.
Show author(s) (2015). An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Algorithmica. 836-859.

Show author(s) (2014). The parameterized complexity of graph cyclability. Lecture Notes in Computer Science (LNCS). 492-504.
Show author(s) (2014). Subset feedback vertex sets in chordal graphs. Journal of Discrete Algorithms. 7-15.
Show author(s) (2014). Solutions for the stable roommates problem with payments. Theoretical Computer Science. 53-61.
Show author(s) (2014). Recognizing Threshold Tolerance Graphs in O(n^2) Time. Lecture Notes in Computer Science (LNCS). 214-224.
Show author(s) (2014). Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica. 473-497.
Show author(s) (2014). Parameterized complexity of connected even/odd subgraph problems. Journal of computer and system sciences. 157-179.
Show author(s) (2014). Parameterized algorithms to preserve connectivity. Lecture Notes in Computer Science (LNCS). 800-811.
Show author(s) (2014). On Recognition of Threshold Tolerance Graphs and their Complements. Lecture Notes in Computer Science (LNCS). 214-224.
Show author(s) (2014). Long circuits and large euler subgraphs. SIAM Journal on Discrete Mathematics. 878-892.
Show author(s) (2014). List coloring in the absence of two subgraphs. Discrete Applied Mathematics. 123-130.
Show author(s) (2014). Lift-contractions. European journal of combinatorics (Print). 286-296.
Show author(s) (2014). Induced disjoint paths in circular-arc graphs in linear time. Lecture Notes in Computer Science (LNCS). 225-237.
Show author(s) (2014). Finding clubs in graph classes. Discrete Applied Mathematics. 57-65.
Show author(s) (2014). Editing to a Graph of Given Degrees. Lecture Notes in Computer Science (LNCS). 196-207.
Show author(s) (2014). Editing to Eulerian graphs. Leibniz International Proceedings in Informatics. 97-108.
Show author(s) (2014). Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica. 501-521.
Show author(s) (2014). Connecting vertices by independent trees. Leibniz International Proceedings in Informatics. 73-84.
Show author(s) (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science. 34-43.
Show author(s) (2014). Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics. 107-120.
Show author(s) (2014). Closing complexity gaps for coloring problems on H-free graphs. Information and Computation. 204-214.
Show author(s) (2014). An incremental polynomial time Algorithm to enumerate all minimal edge dominating sets. Algorithmica. 836-859.
Show author(s) (2014). An exact algorithm for Subset Feedback Vertex Set on chordal graphs. Journal of Discrete Algorithms. 7-15.
Show author(s) (2014). Almost optimal lower bounds for problems parameterized by clique-width. SIAM journal on computing (Print). 1541-1563.

Show author(s) (2013). Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Theoretical Computer Science. 69-84.
Show author(s) (2013). Three complexity results on coloring Pk-free graphs. European journal of combinatorics (Print). 609-619.
Show author(s) (2013). Preventing unraveling in social networks gets harder.
Show author(s) (2013). Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. 12 pages.
Show author(s) (2013). Obtaining planarity by contracting few edges. Theoretical Computer Science. 38-46.
Show author(s) (2013). Modifying a Graph Using Vertex Elimination. Algorithmica.
Show author(s) (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science. 20-32.
Show author(s) (2013). Choosability on H-free graphs. Information Processing Letters. 107-110.

Show author(s) (2012). k-Gap Interval Graphs. Lecture Notes in Computer Science (LNCS). 350-361.
Show author(s) (2012). Parameterized complexity of the spanning tree congestion problem. Algorithmica. 85-111.
Show author(s) (2012). Obtaining planarity by contracting few edges. Lecture Notes in Computer Science (LNCS). 455-466.
Show author(s) (2012). Minimizing Rosenthal potential in multicast games. Lecture Notes in Computer Science (LNCS).
Show author(s) (2012). How to Eliminate a Graph. Lecture Notes in Computer Science (LNCS). 320-331.
Show author(s) (2012). Edge search number of cographs. Discrete Applied Mathematics. 734-743.
Show author(s) (2012). Detecting Induced Minors in AT-Free Graphs. Lecture Notes in Computer Science (LNCS). 495-505.
Show author(s) (2012). Cops and robber with constraints. SIAM Journal on Discrete Mathematics. 571-590.
Show author(s) (2012). Cops and robber game without recharging. Theory of Computing Systems. 611-620.
Show author(s) (2012). Coloring Graphs Characterized by a Forbidden Subgraph. Lecture Notes in Computer Science (LNCS). 443-454.
Show author(s) (2012). Closing Complexity Gaps for Coloring Problems on H-Free Graphs. Lecture Notes in Computer Science (LNCS). 14-23.
Show author(s) (2012). An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs. Lecture Notes in Computer Science (LNCS). 85-96.

Show author(s) (2011). Spanners of bounded degree graphs. Information Processing Letters. 142-144.
Show author(s) (2011). Spanners in sparse graphs. Journal of computer and system sciences. 1108-1119.
Show author(s) (2011). How to Guard a Graph? Algorithmica. 839-856.
Show author(s) (2011). Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 6484-6497.
Show author(s) (2011). Contraction obstructions for treewidth. Journal of combinatorial theory. Series B (Print). 302-314.
Show author(s) (2011). Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica. 252-273.
Show author(s) (2011). Bandwidth on AT-free graphs. Theoretical Computer Science. 7001-7008.
Show author(s) (2011). Approximation of minimum weight spanners for sparse graphs. Theoretical Computer Science. 846-852.
Show author(s) (2011). Approximating width parameters of hypergraphs with excluded minors. SIAM Journal on Discrete Mathematics. 1331-1348.

Show author(s) (2010). Pursuing a fast robber on a graph. Theoretical Computer Science. 1167-1181.
Show author(s) (2010). Intractability of clique-width parameterizations. SIAM journal on computing (Print). 1941-1956.
Show author(s) (2010). Complexity of the packing coloring problem for trees. Discrete Applied Mathematics. 771-778.

Show author(s) (2009). Three Complexity Results on Coloring Pk-Free Graphs. Lecture Notes in Computer Science (LNCS). 95-104.
Show author(s) (2009). The capture time of a graph. Discrete Mathematics. 5588-5595.
Show author(s) (2009). Sort and Search: Exact algorithms for generalized domination. Information Processing Letters. 795-798.
Show author(s) (2009). Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms. Lecture Notes in Computer Science (LNCS). 210-221.
Show author(s) (2009). Parameterized Complexity of Generalized Domination Problems. Lecture Notes in Computer Science (LNCS). 133-142.
Show author(s) (2009). Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. Lecture Notes in Computer Science (LNCS). 221-230.
Show author(s) (2009). Induced Packing of Odd Cycles in a Planar Graph. Lecture Notes in Computer Science (LNCS). 514-523.
Show author(s) (2009). Contraction Bidimensionality: The Accurate Picture. Lecture Notes in Computer Science (LNCS). 706-717.
Show author(s) (2009). Choosability of P5-free graphs. Lecture Notes in Computer Science (LNCS). 382-391.
Show author(s) (2009). Bandwidth on AT-Free Graphs. Lecture Notes in Computer Science (LNCS). 573-582.
Show author(s) (2009). Approximating Acyclicity Parameters of Sparse Hypergraphs. Leibniz International Proceedings in Informatics. 445-456.

Show author(s) (2008). Spanners in sparse graphs. Lecture Notes in Computer Science (LNCS). 597-608.
Show author(s) (2008). Parameterized complexity for domination problems on degenerate graphs. Lecture Notes in Computer Science (LNCS). 195-205.
Show author(s) (2008). On tractability cops and robbers game. IFIP International Federation for Information Processing. 171-185.
Show author(s) (2008). How to guard a graph? Lecture Notes in Computer Science (LNCS). 318-239.
Show author(s) (2008). Generalized domination in degenerate graphs: a complete dichotomy of computational complexity. Lecture Notes in Computer Science (LNCS). 182-191.
Show author(s) (2008). Distance constrained labeling of trees. Lecture Notes in Computer Science (LNCS). 125-135.
Show author(s) (2008). Computational complexity of the distance constrained labeling problem for trees. Lecture Notes in Computer Science (LNCS). 294-305.
Show author(s) (2008). Complexity of the packing coloring problem for trees. Lecture Notes in Computer Science (LNCS). 134-145.
Show author(s) (2008). A PTAS for the sparsest spanners problem on apex-minor-free graphs. Lecture Notes in Computer Science (LNCS). 290-298.

Show author(s) (2007). Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs. Lecture Notes in Computer Science (LNCS). 1-11.
Show author(s) (2007). Branch and Recharge: Exact Algorithms for Generalized Domination. Lecture Notes in Computer Science (LNCS). 507-518.
Show author(s) (2007). Backbone colorings for graphs: Tree and path backbones. Journal of Graph Theory. 137-152.

More information in national current research information system (CRIStin)

Fields of competence

Parameterized Complexity