On the complexity of singly connected vertex deletion
From MaRDI portal
Recommendations
- On the Complexity of Singly Connected Vertex Deletion
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
- A complexity dichotomy for finding disjoint solutions of vertex deletion problems
- Tight running time lower bounds for vertex deletion problems
- The complexity of some edge deletion problems
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized complexity of vertex deletion into perfect graph classes
- On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
- A parameterized algorithm for bounded-degree vertex deletion
- Vertex deletion problems on chordal graphs
Cites work
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A 4k^2 kernel for feedback vertex set
- A fixed-parameter algorithm for the directed feedback vertex set problem
- A kernelization algorithm for \(d\)-hitting set
- A naive algorithm for feedback vertex set
- A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
- A partial k-arboretum of graphs with bounded treewidth
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- An \(O(|V|^2)\) algorithm for single connectedness
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Classes of directed graphs
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Determining uni-connectivity in directed graphs
- Digraphs
- Edge-disjoint paths in digraphs with bounded independence number
- Faster deterministic \textsc{Feedback Vertex Set}
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Finding odd cycle transversals.
- Fixed-Parameter Tractability and Completeness I: Basic Results
- scientific article; zbMATH DE number 3165195 (Why is no real title available?)
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 686998 (Why is no real title available?)
- scientific article; zbMATH DE number 1443271 (Why is no real title available?)
- Improved algorithms for feedback vertex set problems
- Kernels for deletion to classes of acyclic digraphs
- Locally Semicomplete Digraphs and Generalizations
- Locally semicomplete digraphs: A generalization of tournaments
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- ON DISJOINT CYCLES
- On feedback vertex set: new measure and new structures
- On testing single connectedness in directed graphs and some related problems
- On the Complexity of Singly Connected Vertex Deletion
- On the feedback vertex set problem in permutation graphs
- Packing directed circuits fractionally
- Parameterized algorithms
- Parameterized and Exact Computation
- Polynomial kernels for deletion to classes of acyclic digraphs
- Reducibility among combinatorial problems
- Towards a polynomial kernel for directed feedback vertex set
- Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS
Cited in
(6)- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness
- On the Complexity of Singly Connected Vertex Deletion
- Vertex deletion on split graphs: beyond 4-hitting set
- Make a graph singly connected by edge orientations
- Towards transitive-free digraphs
This page was built for publication: On the complexity of singly connected vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2089067)
