5 citations · 8 across the 2 of their papers we have counts for
6 papers · 1 filter
Parameterized Aspects of Strong Subgraph Closure
Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis +2
Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized…
Finding Connected Secluded Subgraphs
Petr A. Golovach, Pinar Heggernes, Paloma Lima +1
Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough…
Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch
Connected Vertex Cover is one of the classical problems of computer science, already mentioned in the monograph of Garey and Johnson. Although the optimization and decision variant…
Generating All Minimal Edge Dominating Sets with Incremental-Polynomial Delay
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch +1
For an arbitrary undirected simple graph G with m edges, we give an algorithm with running time O(m^4 |L|^2) to generate the set L of all minimal edge dominating sets of G. For bip…
Contracting Graphs to Paths and Trees
Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque +2
Vertex deletion and edge deletion problems play a central role in Parameterized Complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and…
Obtaining a Bipartite Graph by Contracting Few Edges
Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov +1
We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph and an integer , and the ta…