\(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
DOI10.1016/j.dam.2023.11.048zbMath1530.05185OpenAlexW4389469618MaRDI QIDQ6145821
Dibyayan Chakraborty, L. Sunil Chandran, Sajith Padinhatteeri, Raji R. Pillai
Publication date: 9 January 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2023.11.048
interval graphscluster vertex deletionvertex deletion problem\(s\)-club cluster vertex deletionwell-partitioned chordal graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)
Cites Work
- A fast branching algorithm for cluster vertex deletion
- Graph-based data clustering with overlaps
- Approximate association via dissociation
- Correlation clustering
- Fixed-parameter algorithms for cluster vertex deletion
- The node-deletion problem for hereditary properties is NP-complete
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Vertex deletion problems on chordal graphs
- Automated generation of search tree algorithms for hard graphs modification problems
- Cluster graph modification problems
- Algorithmic graph theory and perfect graphs
- Faster parameterized algorithm for cluster vertex deletion
- Algorithms and complexity of \(s\)-club cluster vertex deletion
- Well-partitioned chordal graphs
- Improved approximation algorithms for hitting 3-vertex paths
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Novel approaches for analyzing biological networks
- On Editing Graphs into 2-Club Clusters
- The Cluster Editing Problem: Implementations and Experiments
- A graph‐theoretic definition of a sociometric clique†
- A Faster Deterministic Maximum Flow Algorithm
- Subquadratic Kernels for Implicit 3-H <scp>itting</scp> S <scp>et</scp> and 3-S <scp>et</scp> P <scp>acking</scp> Problems
- On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
- Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs
- Exact Algorithms via Monotone Local Search
- Node-and edge-deletion NP-complete problems
- A tight approximation algorithm for the cluster vertex deletion problem
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
