On the Complexity of Singly Connected Vertex Deletion
From MaRDI portal
Publication:5041193
DOI10.1007/978-3-030-48966-3_18OpenAlexW3029825649MaRDI QIDQ5041193
Nidhi Purohit, Jayakrishnan Madathil, Lawqueen Kanesh, Avinandan Das, Saket Saurabh, Komal Muluk
Publication date: 13 October 2022
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-48966-3_18
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- Edge-disjoint paths in digraphs with bounded independence number
- On feedback vertex set: new measure and new structures
- A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
- Finding odd cycle transversals.
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Improved algorithms for feedback vertex set problems
- A kernelization algorithm for \(d\)-hitting set
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Determining uni-connectivity in directed graphs
- On the feedback vertex set problem in permutation graphs
- An \(O(|V|^2)\) algorithm for single connectedness
- Kernels for deletion to classes of acyclic digraphs
- Polynomial kernels for deletion to classes of acyclic digraphs
- Packing directed circuits fractionally
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Faster deterministic \textsc{Feedback Vertex Set}
- Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS
- On testing single connectedness in directed graphs and some related problems
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- Graph Theory
- A 4 k 2 kernel for feedback vertex set
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Locally Semicomplete Digraphs and Generalizations
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Locally semicomplete digraphs: A generalization of tournaments
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- ON DISJOINT CYCLES
- Classes of Directed Graphs
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Reducibility among Combinatorial Problems
- A naive algorithm for feedback vertex set
- Parameterized and Exact Computation
