3 citations · 3 across the 1 of their papers we have counts for
3 papers · 1 filter
(In)approximability of Maximum Minimal FVS
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei +2
We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between…
Extension of vertex cover and independent set in some classes of graphs and generalizations
Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei +2
We consider extension variants of the classical graph problems Vertex Cover and Independent Set. Given a graph and a vertex set , it is asked if there exis…
On the Complexity of Solution Extension of Optimization Problems
Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei +2
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating min…