scientific article; zbMATH DE number 1182772
From MaRDI portal
Publication:4400856
zbMath0911.90340MaRDI QIDQ4400856
Publication date: 5 May 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
semidefinite programmingrandomized roundingpolynomial-time approximation schemeheaviest \(k\)-vertex induced subgraph
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items
Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset, Sensor network localization, Euclidean distance matrix completions, and graph realization, Finding connected \(k\)-subgraphs with high density, Finding Connected Dense $$k$$-Subgraphs, Approximation with a fixed number of solutions of some multiobjective maximization problems, On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems, The densest \(k\)-subgraph problem on clique graphs, Discrete location problems with push-pull objectives, Semi-definite relaxation algorithm of multiple knapsack problem, Upper bounds and exact algorithms for \(p\)-dispersion problems, The complexity of detecting fixed-density clusters, Approximating \(k\)-forest with resource augmentation: a primal-dual approach, Variable neighborhood search for the heaviest \(k\)-subgraph, On approximation of max-vertex-cover, Unnamed Item, Improved approximation algorithms for maximum graph partitioning problems
