The maximum independent union of cliques problem: complexity and exact approaches
DOI10.1007/S10898-018-0694-2zbMATH Open1448.90093OpenAlexW2885685052WikidataQ129420189 ScholiaQ129420189MaRDI QIDQ2174276FDOQ2174276
Authors: Zeynep Ertem, Eugene Lykhovyd, Sergiy Butenko, Yiming 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
Recommendations
- Polyhedral properties of the induced cluster subgraphs
- A fast algorithm for the maximum clique problem
- Strong triadic closure in cographs and graphs of low maximum degree
- scientific article; zbMATH DE number 753971
- Improved approximations of independent sets in bounded-degree graphs
- scientific article; zbMATH DE number 522858
- Maximum colorful independent sets in vertex-colored graphs
- Strong triadic closure in cographs and graphs of low maximum degree
- Approximating maximum independent sets by excluding subgraphs
- A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)
Cites Work
- An enhanced bitstring encoding for exact maximum clique search in sparse graphs
- The maximum clique problem
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Cluster editing with locally bounded modifications
- Fixed-parameter algorithms for cluster vertex deletion
- Claw-free graphs---a survey
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Probabilistic checking of proofs
- Planar Formulae and Their Uses
- Approximation algorithms for NP-complete problems on planar graphs
- Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
- Node-and edge-deletion NP-complete problems
- Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
- Cluster graph modification problems
- On graphs with polynomially solvable maximum-weight clique problem
- Russian doll search for the Steiner triple covering problem
- Even faster parameterized cluster deletion and cluster editing
- The Cluster Editing Problem: Implementations and Experiments
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster 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
- Improved approximation algorithms for hitting 3-vertex paths
- Approximate association via dissociation
- A fast branching algorithm for cluster vertex deletion
- On connected dominating sets of restricted diameter
- On the Maximum Weight Clique Problem
- Exact algorithms via monotone local search
- Title not available (Why is that?)
- Efficient algorithms for cluster editing
- The disjoint cliques problem
- Maximum weight relaxed cliques and Russian doll search revisited
- On a polynomial fractional formulation for independence number of a graph
- The maximum number of induced open triangles in graphs of a given order
- Subquadratic kernels for implicit 3-hitting set and 3-set packing problems
Cited In (10)
- Finding independent sets in unions of perfect graphs
- Maximizing dominance in the plane and its applications
- hClique: An exact algorithm for maximum clique problem in uniform hypergraphs
- Polyhedral properties of the induced cluster subgraphs
- On NP-hardness of the clique partition -- independence number gap recognition and related problems
- Asymptotic bounds for clustering problems in random graphs
- An improved approximation for maximum \(k\)-dependent set on bipartite graphs
- On the complexity of finding a potential community
- Learning driven three-phase search for the maximum independent union of cliques problem
- On independent cliques and linear complementarity problems
Uses Software
This page was built for publication: The maximum independent union of cliques problem: complexity and exact approaches
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174276)
