Algorithms and complexity of s-club cluster vertex deletion

DOI10.1007/978-3-030-79987-8_11MaRDI QIDQ2115849zbMATH OpenOpenAlexFDO

Authors Dibyayan Chakraborty, L. Sunil Chandran, Sajith Padinhatteeri, Raji R. Pillai

Publication date 22 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-79987-8_11

zbMATH Keywords

APX-hardnessNP-hardnesspolynomial-time algorithmssplit graphstrapezoid graphs\(s\)-clubvertex deletion problem(planar) bipartite graphs

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(7)

• 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
• \(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 tractability of covering a graph with 2-clubs
• On the \(d\)-claw vertex deletion problem

Describes a project that uses

Uses Software

• solverALL

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)