scientific article; zbMATH DE number 1182772

zbMath0911.90340MaRDI QIDQ4400856

Anand Srivastav, Katja Wolf

Publication date: 5 May 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

semidefinite programmingrandomized roundingpolynomial-time approximation schemeheaviest \(k\)-vertex induced subgraph

Mathematics Subject Classification ID

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