Cluster deletion on interval graphs and split related graphs

DOI10.1007/S00453-021-00817-8MaRDI QIDQ2037103zbMATH OpenOpenAlexFDO

Authors Athanasios L. Konstantinidis, Charis Papadopoulos

Publication date 30 June 2021

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.09470, https://drops.dagstuhl.de/opus/volltexte/2019/10956/

zbMATH Keywords

cluster deletion probleminterval graphssplit graphs

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Cluster deletion revisited
• The cluster deletion problem for cographs
• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
• Cluster graph modification problems

Cites work

• A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Characterizing intersection graphs of substars of a star.
• Cluster analysis and mathematical programming
• Cluster deletion on interval graphs and split related graphs
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Clustering with qualitative information
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Correlation clustering
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Generalized graph clustering: recognizing (p,q)-cluster graphs
• Graph Classes: A Survey
• Graph clustering
• scientific article; zbMATH DE number 3579840 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Incidence matrices and interval graphs
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• On the clique-width of some perfect graph classes
• Parameterized aspects of strong subgraph closure
• Solving partition problems almost always requires pushing many vertices around
• Strong triadic closure in cographs and graphs of low maximum degree
• The cluster deletion problem for cographs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The splittance of a graph

Cited in

(17)

• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
• A polynomial algorithm for the k-cluster problem on the interval graphs
• The cluster deletion problem for cographs
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Cluster deletion on interval graphs and split related graphs
• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
• Parameterized complexity of multicut in weighted trees
• Structural parameterization of cluster deletion
• \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• When can cluster deletion with bounded weights be solved efficiently?
• Domination and cut problems on chordal graphs with bounded leafage
• Structural parameterization of cluster deletion
• Graph clustering problems under the Lens of parameterized local search
• When can cluster deletion with bounded weights be solved efficiently?
• Cluster editing on cographs and related classes

This page was built for publication: Cluster deletion on interval graphs and split related graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037103)