On cycle transversals and their connected variants in the absence of a small linear forest
type: Item
instance of: scholarly article
title: On cycle transversals and their connected variants in the absence of a small linear forest
zbMATH Open document ID: 1459.05332
author: Konrad Dabrowski
author: Carl Feghali
author: Matthew Johnson
author: Giacomo Paesani
author: Daniël Paulusma
author: Paweł Rzążewski
published in: Algorithmica
publication date: 2020-10-12T00:00:00Z
Mathematics Subject Classification ID: 05D15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7259196
zbMATH Keywords: odd cycle transversal
zbMATH Keywords: feedback vertex set
zbMATH Keywords: \(H\)-free graph
zbMATH Keywords: connected transversal
MaRDI profile type: Publication
full work available at URL: s00453-020-00706-6
OpenAlex ID: W2965619982
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: The price of connectivity for feedback vertex set
cites work: Independent feedback vertex set for \(P_5\)-free graphs
cites work: Q3694712
cites work: Graph Classes: A Survey
cites work: Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
cites work: The Price of Connectivity for Vertex Cover
cites work: The price of connectivity for dominating set: upper bounds and complexity
cites work: Connected vertex covers in dense graphs
cites work: Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
cites work: Parameterized Algorithms
cites work: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
cites work: On cycle transversals and their connected variants in the absence of a small linear forest
cites work: Vertex and edge covers with clustering properties: Complexity and algorithms
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Some simplified NP-complete graph problems
cites work: A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
cites work: Connected Feedback Vertex Set in Planar Graphs
cites work: \(H\)-colouring \(P_t\)-free graphs in subexponential time
cites work: Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs
cites work: The price of connectivity for cycle transversals
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Connected vertex cover for \((sP_1+P_5)\)-free graphs
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: On parameterized independent feedback vertex set
cites work: Stable sets for (P_{6}, K_{2,3})-free graphs
cites work: Boundary classes for graph problems involving non-local properties
cites work: Subexponential algorithms for variants of the homomorphism problem in string graphs
cites work: Q4770411
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: Q3318125
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
DOI: 10.1007/S00453-020-00706-6
description: scientific article; zbMATH DE number 7259196