Vertex deletion on split graphs: beyond 4-hitting set
From MaRDI portal
Publication:5918994
DOI10.1016/j.tcs.2020.08.028zbMath1462.68137OpenAlexW3081992751MaRDI QIDQ5918994
R. Krithika, Pratibha Choudhary, Pallavi Jain, Vibha Sahlot
Publication date: 22 October 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.08.028
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Rainbow colouring of split graphs
- Fundamentals of parameterized complexity
- Complexity of the cluster deletion problem on subclasses of chordal graphs
- Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
- On the hardness of approximating minimum vertex cover
- Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph
- A characterization of block graphs
- On the spectral radius of (0,1)-matrices
- Distance-hereditary graphs
- The node-deletion problem for hereditary properties is NP-complete
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
- On the threshold of intractability
- Iterative compression and exact algorithms
- Faster parameterized algorithms for deletion to split graphs
- A polynomial kernel for block graph deletion
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parametrized complexity theory.
- Complexity of Steiner Tree in Split Graphs - Dichotomy Results
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- The Design of Approximation Algorithms
- Cutwidth of Split Graphs and Threshold Graphs
- Node-Deletion Problems on Bipartite Graphs
- Computing the Minimum Fill-In is NP-Complete
- Oriented Threshold Graphs
- Kernelization
- Vertex Deletion Problems on Chordal Graphs
- Exact Algorithms via Monotone Local Search
- Parameterized Algorithms
