Algorithms and complexity of s-club cluster vertex deletion
From MaRDI portal
Publication:2115849
DOI10.1007/978-3-030-79987-8_11OpenAlexW3176095703MaRDI QIDQ2115849FDOQ2115849
L. Sunil Chandran, Sajith Padinhatteeri, Raji R. Pillai, Dibyayan Chakraborty
Publication date: 22 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-79987-8_11
APX-hardnessNP-hardnesspolynomial-time algorithmssplit graphstrapezoid graphs\(s\)-clubvertex deletion problem(planar) bipartite graphs
Cites Work
- Title not available (Why is that?)
- Fixed-parameter algorithms for cluster vertex deletion
- The node-deletion problem for hereditary properties is NP-complete
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Novel approaches for analyzing biological networks
- Node-and edge-deletion NP-complete problems
- Trapezoid graphs and generalizations, geometry and algorithms
- Parameterized computational complexity of finding small-diameter subgraphs
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- An efficient algorithm for finding all hinge vertices on trapezoid graphs
- On structural parameterizations for the 2-club problem
- Approximating Maximum Diameter-Bounded Subgraphs
- An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
- The recognition of triangle graphs
- Finding large \(k\)-clubs in undirected graphs
- Distances in cocomparability graphs and their powers
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Linear Time LexDFS on Cocomparability Graphs.
- On Editing Graphs into 2-Club Clusters
- Vertex deletion problems on chordal graphs
- A recognition algorithm for simple-triangle graphs
Cited In (7)
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- On the parameterized complexity of s-club cluster deletion problems
- On the parameterized complexity of \(s\)-club cluster deletion problems
- Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
- On the \(d\)-claw vertex deletion problem
- On the tractability of covering a graph with 2-clubs
Uses Software
This page was built for publication: Algorithms and complexity of \(s\)-club cluster vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115849)
