Finding dense subgraphs with semidefinite programming (extended abstract)

DOI10.1007/BFB0053974MaRDI QIDQ4400856zbMATH OpenFDO

Authors Anand Srivastav, Katja Wolf

Publication date 5 May 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0053974

zbMATH Keywords

heaviest \(k\)-vertex induced subgraphpolynomial-time approximation schemerandomized roundingsemidefinite programming

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The dense \(k\)-subgraph problem
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Greedily Finding a Dense Subgraph
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation of dense-n/2-subgraph and the complement of min-bisection

Cited in

(27)

• Variable neighborhood search for the heaviest \(k\)-subgraph
• A note on the approximability of the dense subgraph problem.
• Approximation of dense-n/2-subgraph and the complement of min-bisection
• On approximation of max-vertex-cover
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Finding connected \(k\)-subgraphs with high density
• The densest \(k\)-subgraph problem on clique graphs
• Upper bounds and exact algorithms for \(p\)-dispersion problems
• The complexity of detecting fixed-density clusters
• Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
• Finding Connected Dense k-Subgraphs
• 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
• Approximation with a fixed number of solutions of some multiobjective maximization problems
• Greedily Finding a Dense Subgraph
• Dense subgraph problems with output-density conditions
• Discounted average degree density metric and new algorithms for the densest subgraph problem
• Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• scientific article; zbMATH DE number 7765378 (Why is no real title available?)
• Sum-of-squares lower bounds for densest k-subgraph
• Planted models for the densest k-subgraph problem
• Discrete location problems with push-pull objectives
• Semi-definite relaxation algorithm of multiple knapsack problem
• Improved approximation algorithms for maximum graph partitioning problems
• Approximation of dense-\(\frac n2\)-subgraph and table compression problems
• On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems

This page was built for publication: Finding dense subgraphs with semidefinite programming (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4400856)