Petr A. Golovach

According to our database1, Petr A. Golovach authored at least 172 papers between 1998 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Approximation Schemes for Low-rank Binary Matrix Approximation Problems.
ACM Trans. Algorithms, 2020

On the Parameterized Complexity of Graph Modification to First-Order Logic Properties.
Theory Comput. Syst., 2020

Finding connected secluded subgraphs.
J. Comput. Syst. Sci., 2020

Parameterized low-rank binary matrix approximation.
Data Min. Knowl. Discov., 2020

Enumeration of minimal connected dominating sets for chordal graphs.
Discret. Appl. Math., 2020

EPTAS for k-means Clustering of Affine Subspaces.
CoRR, 2020

Graph Square Roots of Small Distance from Degree One Graphs.
CoRR, 2020

Diverse Pairs of Matchings.
CoRR, 2020

A survey of parameterized algorithms and the complexity of edge modification.
CoRR, 2020

Parameterized Aspects of Strong Subgraph Closure.
Algorithmica, 2020

Subgraph Complementation.
Algorithmica, 2020

On the Tractability of Optimization Problems on H-Graphs.
Algorithmica, 2020

Parameterized Complexity of PCA (Invited Talk).
Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Parameterization Above a Multiplicative Guarantee.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

On the Complexity of Recovering Incidence Matrices.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Kernelization of Whitney Switches.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Low-Rank Binary Matrix Approximation in Column-Sum Norm.
Proceedings of the Approximation, 2020

2019
Enumeration of maximal irredundant sets for claw-free graphs.
Theor. Comput. Sci., 2019

Enumeration and maximum number of minimal dominating sets for chordal graphs.
Theor. Comput. Sci., 2019

Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring.
ACM Trans. Algorithms, 2019

Spanning Circuits in Regular Matroids.
ACM Trans. Algorithms, 2019

Editing to Connected F-Degree Graph.
SIAM J. Discret. Math., 2019

Enumeration and maximum number of maximal irredundant sets for chordal graphs.
Discret. Appl. Math., 2019

Parameterized k-Clustering: The distance matters!
CoRR, 2019

Surjective H-colouring: New hardness results.
Comput., 2019

Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2.
Algorithmica, 2019

Kernelization of Graph Hamiltonicity: Proper H-Graphs.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Modification to Planarity is Fixed Parameter Tractable.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Clustering to Given Connectivities.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

Cyclability in Graph Classes.
Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

Refined Complexity of PCA with Outliers.
Proceedings of the 36th International Conference on Machine Learning, 2019

Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Parameterized k-Clustering: Tractability Island.
Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Going Far From Degeneracy.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018
Structured Connectivity Augmentation.
SIAM J. Discret. Math., 2018

Covering Vectors by Spaces: Regular Matroids.
SIAM J. Discret. Math., 2018

Finding Cactus Roots in Polynomial Time.
Theory Comput. Syst., 2018

Enumeration and maximum number of minimal connected vertex covers in graphs.
Eur. J. Comb., 2018

Computing square roots of graphs with low maximum degree.
Discret. Appl. Math., 2018

Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximativ (Dagstuhl Seminar 18421).
Dagstuhl Reports, 2018

Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width.
Algorithmica, 2018

Partial Complementation of Graphs.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
Graph editing to a given degree sequence.
Theor. Comput. Sci., 2017

A linear kernel for finding square roots of almost planar graphs.
Theor. Comput. Sci., 2017

The Parameterized Complexity of Graph Cyclability.
SIAM J. Discret. Math., 2017

Metric Dimension of Bounded Tree-length Graphs.
SIAM J. Discret. Math., 2017

Parameterized Complexity of Secluded Connectivity Problems.
Theory Comput. Syst., 2017

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs.
J. Graph Theory, 2017

Editing to a planar graph of given degrees.
J. Comput. Syst. Sci., 2017

Editing to a connected graph of given degrees.
Inf. Comput., 2017

Graph editing to a fixed target.
Discret. Appl. Math., 2017

On recognition of threshold tolerance graphs and their complements.
Discret. Appl. Math., 2017

Minimal dominating sets in interval graphs and trees.
Discret. Appl. Math., 2017

Parameterized Complexity of Superstring Problems.
Algorithmica, 2017

2016
Induced disjoint paths in circular-arc graphs in linear time.
Theor. Comput. Sci., 2016

Enumerating minimal connected dominating sets in graphs of bounded chordality.
Theor. Comput. Sci., 2016

Editing to Eulerian graphs.
J. Comput. Syst. Sci., 2016

Parameterized complexity of the anchored k-core problem for directed graphs.
Inf. Comput., 2016

Squares of Low Clique Number.
Electron. Notes Discret. Math., 2016

How to hunt an invisible rabbit on a graph.
Eur. J. Comb., 2016

Enumerating minimal dominating sets in chordal bipartite graphs.
Discret. Appl. Math., 2016

Squares of Low Maximum Degree.
CoRR, 2016

Parameterized Algorithms for Finding Square Roots.
Algorithmica, 2016

2015
Editing to a Graph of Given Degrees.
Theor. Comput. Sci., 2015

Induced Disjoint Paths in Claw-Free Graphs.
SIAM J. Discret. Math., 2015

Hadwiger Number of Graphs with Small Chordality.
SIAM J. Discret. Math., 2015

Minimizing Rosenthal Potential in Multicast Games.
Theory Comput. Syst., 2015

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.
J. Graph Theory, 2015

Coloring graphs characterized by a forbidden subgraph.
Discret. Appl. Math., 2015

An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets.
Algorithmica, 2015

Modifying a Graph Using Vertex Elimination.
Algorithmica, 2015

List Coloring in the Absence of a Linear Forest.
Algorithmica, 2015

Metric Dimension of Bounded Width Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Variants of Plane Diameter Completion.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

2014
Colouring of graphs with Ramsey-type forbidden subgraphs.
Theor. Comput. Sci., 2014

Solutions for the stable roommates problem with payments.
Theor. Comput. Sci., 2014

Long Circuits and Large Euler Subgraphs.
SIAM J. Discret. Math., 2014

Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width.
SIAM J. Comput., 2014

Subset feedback vertex sets in chordal graphs.
J. Discrete Algorithms, 2014

Parameterized complexity of connected even/odd subgraph problems.
J. Comput. Syst. Sci., 2014

Closing complexity gaps for coloring problems on H-free graphs.
Inf. Comput., 2014

Coloring graphs without short cycles and long induced paths.
Discret. Appl. Math., 2014

List coloring in the absence of two subgraphs.
Discret. Appl. Math., 2014

Finding clubs in graph classes.
Discret. Appl. Math., 2014

A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs.
CoRR, 2014

Detecting Fixed Patterns in Chordal Graphs in Polynomial Time.
Algorithmica, 2014

Parameterized complexity of three edge contraction problems with degree constraints.
Acta Informatica, 2014

Recognizing Threshold Tolerance Graphs in O(n<sup>2</sup>) Time.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Parameterized Algorithms to Preserve Connectivity.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Connecting Vertices by Independent Trees.
Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

2013
Increasing the minimum degree of a graph by contractions.
Theor. Comput. Sci., 2013

Detecting induced minors in AT-free graphs.
Theor. Comput. Sci., 2013

Obtaining planarity by contracting few edges.
Theor. Comput. Sci., 2013

Tight complexity bounds for FPT subgraph problems parameterized by the clique-width.
Theor. Comput. Sci., 2013

Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds.
Theory Comput. Syst., 2013

Choosability on H-free graphs.
Inf. Process. Lett., 2013

Three complexity results on coloring Pk-free graphs.
Eur. J. Comb., 2013

4-coloring H-free graphs when H is small.
Discret. Appl. Math., 2013

Sparse Square Roots.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

On the Parameterized Complexity of Cutting a Few Vertices from a Graph.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Cliques and Clubs.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

Preventing Unraveling in Social Networks Gets Harder.
Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

2012
Computing vertex-surjective homomorphisms to partially reflexive trees.
Theor. Comput. Sci., 2012

Induced packing of odd cycles in planar graphs.
Theor. Comput. Sci., 2012

Determining the chromatic number of triangle-free 2P<sub>3</sub>-free graphs in polynomial time.
Theor. Comput. Sci., 2012

Updating the complexity status of coloring graphs without a fixed induced linear forest.
Theor. Comput. Sci., 2012

Cops and Robber with Constraints.
SIAM J. Discret. Math., 2012

Cops and Robber Game Without Recharging.
Theory Comput. Syst., 2012

On the parameterized complexity of coloring graphs in the absence of a linear forest.
J. Discrete Algorithms, 2012

Parameterized complexity of generalized domination problems.
Discret. Appl. Math., 2012

Containment relations in split graphs.
Discret. Appl. Math., 2012

Edge search number of cographs.
Discret. Appl. Math., 2012

Distance three labelings of trees.
Discret. Appl. Math., 2012

Generating All Minimal Edge Dominating Sets with Incremental-Polynomial Delay
CoRR, 2012

Parameterized Complexity of the Spanning Tree Congestion Problem.
Algorithmica, 2012

Finding vertex-surjective graph homomorphisms.
Acta Informatica, 2012

How to Eliminate a Graph.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Induced Disjoint Paths in AT-Free Graphs.
Proceedings of the Algorithm Theory - SWAT 2012, 2012

k-Gap Interval Graphs.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011
Bandwidth on AT-free graphs.
Theor. Comput. Sci., 2011

Guard games on graphs: Keep the intruder out!
Theor. Comput. Sci., 2011

Parameterized complexity of coloring problems: Treewidth versus vertex cover.
Theor. Comput. Sci., 2011

Approximation of minimum weight spanners for sparse graphs.
Theor. Comput. Sci., 2011

Approximating Width Parameters of Hypergraphs with Excluded Minors.
SIAM J. Discret. Math., 2011

Contraction obstructions for treewidth.
J. Comb. Theory, Ser. B, 2011

Spanners in sparse graphs.
J. Comput. Syst. Sci., 2011

Spanners of bounded degree graphs.
Inf. Process. Lett., 2011

Lift Contractions.
Electron. Notes Discret. Math., 2011

Paths of bounded length and their cuts: Parameterized complexity and algorithms.
Discret. Optim., 2011

Branch and Recharge: Exact Algorithms for Generalized Domination.
Algorithmica, 2011

How to Guard a Graph?
Algorithmica, 2011

Contracting a Chordal Graph to a Split Graph or a Tree.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Odd cyclic surface separators in planar graphs.
Proceedings of the 10th Cologne-Twente Workshop on graphs and combinatorial optimization. Extended Abstracts, 2011

2010
Pursuing a fast robber on a graph.
Theor. Comput. Sci., 2010

Intractability of Clique-Width Parameterizations.
SIAM J. Comput., 2010

Parameterized algorithm for eternal vertex cover.
Inf. Process. Lett., 2010

Complexity of the packing coloring problem for trees.
Discret. Appl. Math., 2010

Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Narrowing Down the Gap on the Complexity of Coloring <i>P</i><sub><i>k</i></sub>-Free Graphs.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Approximation Algorithms for Domination Search.
Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

<i>L</i>(2, 1, 1)-Labeling Is NP-Complete for Trees.
Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

Algorithmic Lower Bounds for Problems Parameterized with Clique-Width.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On Coloring Graphs without Induced Forests.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

2009
Sort and Search: Exact algorithms for generalized domination.
Inf. Process. Lett., 2009

The capture time of a graph.
Discret. Math., 2009

Approximating Acyclicity Parameters of Sparse Hypergraphs.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Clique-width: on the price of generality.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Choosability of P5-Free Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Three Complexity Results on Coloring <i>P</i><sub><i>k</i></sub>-Free Graphs.
Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

Induced Packing of Odd Cycles in a Planar Graph.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Contraction Bidimensionality: the Accurate Picture.
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

2008
Parameterized Complexity for Domination Problems on Degenerate Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity.
Proceedings of the Theory and Applications of Models of Computation, 2008

Distance Constrained Labelings of Trees.
Proceedings of the Theory and Applications of Models of Computation, 2008

A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

On tractability of Cops and Robbers game.
Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
Backbone colorings for graphs: Tree and path backbones.
J. Graph Theory, 2007

Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007

2005
Distance Constrained Labelings of Graphs of Bounded Treewidth.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004
Elegant Distance Constrained Labelings of Trees.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

2003
Interval degree and bandwidth of a graph.
Discret. Appl. Math., 2003

Backbone Colorings for Networks.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

2000
Graph Searching and Interval Completion.
SIAM J. Discret. Math., 2000

1998
Interval Completion with the Smallest Max-degree.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998


  Loading...