Algorithms and complexity of \(s\)-club cluster vertex deletion

DOI10.1007/978-3-030-79987-8_11OpenAlexW3176095703MaRDI QIDQ2115849

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

zbMATH Keywords

trapezoid graphssplit graphsNP-hardnesspolynomial-time algorithmsAPX-hardness\(s\)-clubvertex deletion problem(planar) bipartite graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (5)

\(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 ⋮ On the tractability of covering a graph with 2-clubs

Uses Software

• solverALL

Cites Work

• Unnamed Item
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• The recognition of triangle graphs
• Finding large \(k\)-clubs in undirected graphs
• Fixed-parameter algorithms for cluster vertex deletion
• The node-deletion problem for hereditary properties is NP-complete
• Distances in cocomparability graphs and their powers
• An efficient algorithm for finding all hinge vertices on trapezoid graphs
• Parameterized computational complexity of finding small-diameter subgraphs
• Vertex deletion problems on chordal graphs
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• A recognition algorithm for simple-triangle graphs
• On structural parameterizations for the 2-club problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Novel approaches for analyzing biological networks
• On Editing Graphs into 2-Club Clusters
• Linear Time LexDFS on Cocomparability Graphs.
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Approximating Maximum Diameter-Bounded Subgraphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Node-and edge-deletion NP-complete problems
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs

This page was built for publication: Algorithms and complexity of \(s\)-club cluster vertex deletion