Approximating Maximum Clique by Removing Subgraphs
From MaRDI portal
Publication:4652632
DOI10.1137/S089548010240415XzbMath1068.05052OpenAlexW2074465184WikidataQ56210406 ScholiaQ56210406MaRDI QIDQ4652632
Publication date: 28 February 2005
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s089548010240415x
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items
Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ A review on algorithms for maximum clique problems ⋮ Algorithmic height compression of unordered trees ⋮ Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs ⋮ A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs ⋮ Ramsey theory and integrality gap for the independent set problem ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ A fast approximation algorithm for the maximum 2-packing set problem on planar graphs ⋮ Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ The minimum spanning tree problem with conflict constraints and its variations ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ Approximating independent set in perturbed graphs ⋮ Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods ⋮ Finding large cliques in sparse semi-random graphs by simple randomized search heuristics ⋮ In search of the densest subgraph ⋮ Unnamed Item ⋮ New tools and connections for exponential-time approximation ⋮ Approximating Independent Set and Coloring in Random Uniform Hypergraphs ⋮ On the independent set problem in random graphs ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth ⋮ Degree-constrained graph orientation: maximum satisfaction and minimum violation
