Approximate association via dissociation
From MaRDI portal
Publication:505447
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
triangle-free graphmodular decompositioncluster vertex deletioncluster graphassociation setdissociation set
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