Approximate association via dissociation

DOI10.1016/j.dam.2016.11.007zbMath1354.05110arXiv1510.08276OpenAlexW4210308458MaRDI QIDQ505447

Jie You, Yixin Cao, Jianxin Wang

Publication date: 23 January 2017

Published in: Discrete Applied Mathematics, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.08276

zbMATH Keywords

triangle-free graphmodular decompositioncluster vertex deletioncluster graphassociation setdissociation set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

The maximum independent union of cliques problem: complexity and exact approaches ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Improved approximation algorithms for hitting 3-vertex paths ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Vertex deletion problems on chordal graphs ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Vertex Deletion Problems on Chordal Graphs

Cites Work

• Unnamed Item
• A fast branching algorithm for cluster vertex deletion
• Structural parameterizations for boxicity
• A survey of the algorithmic aspects of modular decomposition
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Correlation clustering
• Fixed-parameter algorithms for cluster vertex deletion
• The node-deletion problem for hereditary properties is NP-complete
• Modular decomposition and transitive orientation
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graphs indecomposable with respect to the X-join
• Cluster editing: kernelization based on edge cuts
• Quasi-threshold graphs
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Improved approximation algorithms for hitting 3-vertex paths
• Constant thresholds can make target set selection tractable
• Edge deletion problems: branching facilitated by modular decomposition
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Clustering with qualitative information
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• The Comparability Graph of a Tree
• Node-Deletion Problems on Bipartite Graphs
• On the hardness of approximating minimization problems
• Transitiv orientierbare Graphen
• Aggregating inconsistent information