Petr A. Golovach

According to our database1, Petr A. Golovach
  • authored at least 218 papers between 1998 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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. Discrete Math., 2017

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

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

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs.
Journal of 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.
Discrete Applied Mathematics, 2017

On recognition of threshold tolerance graphs and their complements.
Discrete Applied Mathematics, 2017

Minimal dominating sets in interval graphs and trees.
Discrete Applied Mathematics, 2017

Finding Connected Secluded Subgraphs.
CoRR, 2017

Covering vectors by spaces: Regular matroids.
CoRR, 2017

On the tractability of optimization problems on H-graphs.
CoRR, 2017

Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2.
CoRR, 2017

Surjective H-Colouring: New Hardness Results.
CoRR, 2017

Structured Connectivity Augmentation.
CoRR, 2017

Parameterized Complexity of Superstring Problems.
Algorithmica, 2017

Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Spanning Circuits in Regular Matroids.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Covering Vectors by Spaces: Regular Matroids.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Surjective H-Colouring: New Hardness Results.
Proceedings of the Unveiling Dynamics and Complexity, 2017

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs.
Proceedings of the Algorithms and Complexity - 10th International Conference, 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.
Electronic Notes in Discrete Mathematics, 2016

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

Enumerating minimal dominating sets in chordal bipartite graphs.
Discrete Applied Mathematics, 2016

Graph Editing to a Given Degree Sequence.
CoRR, 2016

A Linear Kernel for Finding Square Roots of Almost Planar Graphs.
CoRR, 2016

Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs.
CoRR, 2016

Spanning Circuits in Regular Matroids.
CoRR, 2016

Squares of Low Maximum Degree.
CoRR, 2016

Metric Dimension of Bounded Tree-length Graphs.
CoRR, 2016

Parameterized Algorithms for Finding Square Roots.
Algorithmica, 2016

A Linear Kernel for Finding Square Roots of Almost Planar Graphs.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Editing to Connected f-Degree Graph.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Finding Cactus Roots in Polynomial Time.
Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Graph Editing to a Given Degree Sequence.
Proceedings of the Computer Science - Theory and Applications, 2016

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

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

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

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

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

Coloring graphs characterized by a forbidden subgraph.
Discrete Applied Mathematics, 2015

Variants of Plane Diameter Completion.
CoRR, 2015

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

Parameterized Complexity of Secluded Connectivity Problems.
CoRR, 2015

Editing to a Planar Graph of Given Degrees.
CoRR, 2015

Parameterized Complexity of Superstring Problems.
CoRR, 2015

How to Hunt an Invisible Rabbit on a Graph.
CoRR, 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

Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs.
Proceedings of the Combinatorial Algorithms - 26th International Workshop, 2015

Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Parameterized Complexity of Secluded Connectivity Problems.
Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Editing to a Planar Graph of Given Degrees.
Proceedings of the Computer Science - Theory and Applications, 2015

Parameterized Complexity of Superstring Problems.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

How to Hunt an Invisible Rabbit on a Graph.
Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 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. Discrete 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

Lift-contractions.
Eur. J. Comb., 2014

Coloring graphs without short cycles and long induced paths.
Discrete Applied Mathematics, 2014

List coloring in the absence of two subgraphs.
Discrete Applied Mathematics, 2014

Finding clubs in graph classes.
Discrete Applied Mathematics, 2014

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time.
CoRR, 2014

The Parameterized Complexity of Graph Cyclability.
CoRR, 2014

Hadwiger number of graphs with small chordality.
CoRR, 2014

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

Editing to Eulerian Graphs.
CoRR, 2014

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

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

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Recognizing Threshold Tolerance Graphs in O(n2) Time.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Hadwiger Number of Graphs with Small Chordality.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Editing to a Connected Graph of Given Degrees.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Editing to a Graph of Given Degrees.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

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

Editing to Eulerian Graphs.
Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

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

The Parameterized Complexity of Graph Cyclability.
Proceedings of the Algorithms - ESA 2014, 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.
Discrete Applied Mathematics, 2013

Preventing Unraveling in Social Networks Gets Harder
CoRR, 2013

On the parameterized complexity of cutting a few vertices from a graph
CoRR, 2013

Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
CoRR, 2013

Long Circuits and Large Euler Subgraphs
CoRR, 2013

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
CoRR, 2013

Editing to a Graph of Given Degrees.
CoRR, 2013

Editing to a Connected Graph of Given Degrees.
CoRR, 2013

Minimizing Rosenthal Potential in Multicast Games.
CoRR, 2013

Parameterized Algorithms for Finding Square Roots.
CoRR, 2013

Colouring of Graphs with Ramsey-Type Forbidden Subgraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

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

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.
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

Graph Editing to a Fixed Target.
Proceedings of the Combinatorial Algorithms - 24th International Workshop, 2013

An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

Long Circuits and Large Euler Subgraphs.
Proceedings of the Algorithms - ESA 2013, 2013

List Coloring in the Absence of Two Subgraphs.
Proceedings of the Algorithms and Complexity, 8th International Conference, 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 2P3-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. Discrete 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.
Discrete Applied Mathematics, 2012

Containment relations in split graphs.
Discrete Applied Mathematics, 2012

Edge search number of cographs.
Discrete Applied Mathematics, 2012

Distance three labelings of trees.
Discrete Applied Mathematics, 2012

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

Obtaining Planarity by Contracting Few Edges
CoRR, 2012

Finding vertex-surjective graph homomorphisms
CoRR, 2012

Induced Disjoint Paths in Claw-Free Graphs
CoRR, 2012

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

Finding vertex-surjective graph homomorphisms.
Acta Inf., 2012

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

Solutions for the Stable Roommates Problem with Payments.
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

Parameterized Complexity of Connected Even/Odd Subgraph Problems.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

4-Coloring H-Free Graphs When H Is Small.
Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012

Coloring Graphs Characterized by a Forbidden Subgraph.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Obtaining Planarity by Contracting Few Edges.
Proceedings of the Mathematical Foundations of Computer Science 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

Closing Complexity Gaps for Coloring Problems on H-Free Graphs.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Detecting Induced Minors in AT-Free Graphs.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Minimizing Rosenthal Potential in Multicast Games.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Induced Disjoint Paths in Claw-Free Graphs.
Proceedings of the Algorithms - ESA 2012, 2012

Finding Vertex-Surjective Graph Homomorphisms.
Proceedings of the Computer Science - Theory and Applications, 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. Discrete 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.
Electronic Notes in Discrete Mathematics, 2011

Paths of bounded length and their cuts: Parameterized complexity and algorithms.
Discrete Optimization, 2011

k-Gap Interval Graphs
CoRR, 2011

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

How to Guard a Graph?
Algorithmica, 2011

List Coloring in the Absence of a Linear Forest.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

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

Increasing the Minimum Degree of a Graph by Contractions.
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width.
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

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

Coloring Graphs without Short Cycles and Long Induced Paths.
Proceedings of the Fundamentals of Computation Theory - 18th International Symposium, 2011

Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees.
Proceedings of the Computer Science - Theory and Applications, 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.
Discrete Applied Mathematics, 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 Pk-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

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

Cops and Robber Game without Recharging.
Proceedings of the Algorithm Theory, 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.
Discrete Mathematics, 2009

Parameterized Complexity of Generalized Domination Problems.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Guard Games on Graphs: Keep the Intruder Out!
Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover.
Proceedings of the Theory and Applications of Models of Computation, 6th Annual Conference, 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

Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Three Complexity Results on Coloring Pk-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

Bandwidth on AT-Free Graphs.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Contraction Bidimensionality: The Accurate Picture.
Proceedings of the Algorithms, 2009

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

2008
Approximating acyclicity parameters of sparse hypergraphs
CoRR, 2008

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

Complexity of the Packing Coloring Problem for Trees.
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

How to Guard a Graph?.
Proceedings of the Algorithms and Computation, 19th International Symposium, 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

Spanners in Sparse Graphs.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

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

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

Branch and Recharge: Exact Algorithms for Generalized Domination.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 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.
Discrete Applied Mathematics, 2003

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

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

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


  Loading...