The complexity of detecting fixed-density clusters

DOI10.1016/j.dam.2006.01.005zbMath1103.68096OpenAlexW2048597630MaRDI QIDQ2499577

Sven Kosub, Klaus Holzapfel, Hanjo Täubig, Moritz G. Maaß

Publication date: 14 August 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.01.005

zbMATH Keywords

computational complexitygraph algorithmsdensity-based clusteringfixed-parameter problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Dense subgraphs in random graphs ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications
• Approximating maximum independent sets by excluding subgraphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of finding dense subgraphs
• Recent directions in netlist partitioning: a survey
• A Fast Parametric Maximum Flow Algorithm and Applications
• Greedily Finding a Dense Subgraph
• Maximum dispersion problem in dense graphs
• The dense \(k\)-subgraph problem

This page was built for publication: The complexity of detecting fixed-density clusters