The maximum independent union of cliques problem: complexity and exact approaches
From MaRDI portal
Publication:2174276
DOI10.1007/s10898-018-0694-2zbMath1448.90093OpenAlexW2885685052WikidataQ129420189 ScholiaQ129420189MaRDI QIDQ2174276
Zeynep Ertem, Eugene Lykhovyd, Sergiy I. Butenko, Yi-Ming Wang
Publication date: 21 April 2020
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10898-018-0694-2
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items (5)
Asymptotic bounds for clustering problems in random graphs ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Maximizing dominance in the plane and its applications ⋮ An improved approximation for maximum \(k\)-dependent set on bipartite graphs ⋮ On independent cliques and linear complementarity problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
- Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
- Approximate association via dissociation
- Russian doll search for the Steiner triple covering problem
- Cluster editing with locally bounded modifications
- Fixed-parameter algorithms for cluster vertex deletion
- The maximum clique problem
- Claw-free graphs---a survey
- Maximum weight relaxed cliques and Russian doll search revisited
- Cluster graph modification problems
- Even faster parameterized cluster deletion and cluster editing
- The maximum number of induced open triangles in graphs of a given order
- Improved approximation algorithms for hitting 3-vertex paths
- 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
- On connected dominating sets of restricted diameter
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Convex optimization for the planted \(k\)-disjoint-clique problem
- On a polynomial fractional formulation for independence number of a graph
- The Cluster Editing Problem: Implementations and Experiments
- On the Maximum Weight Clique Problem
- On graphs with polynomially solvable maximum-weight clique problem
- Probabilistic checking of proofs
- Planar Formulae and Their Uses
- Approximation algorithms for NP-complete problems on planar graphs
- The disjoint cliques problem
- A Fast Branching Algorithm for Cluster Vertex Deletion
- Reducibility among Combinatorial Problems
- Exact Algorithms via Monotone Local Search
- An enhanced bitstring encoding for exact maximum clique search in sparse graphs
- Node-and edge-deletion NP-complete problems
- Efficient algorithms for cluster editing
This page was built for publication: The maximum independent union of cliques problem: complexity and exact approaches
