Maximizing edge-ratio is NP-complete

DOI10.1016/J.DAM.2011.07.016MaRDI QIDQ765326zbMATH OpenOpenAlexFDO

Authors Steven D. Noble, Pierre Hansen, Nenad Mladenović

Publication date 19 March 2012

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

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

zbMATH Keywords

graph clusteringcommunity detectionNP-completenessedge-ratio

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 3983202
• The path partition problem and related problems in bipartite graphs
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• Finding good approximate vertex and edge partitions is NP-hard
• Partitioning to three matchings of given size is NP-complete for bipartite graphs

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• On clusterings: good, bad and spectral
• Some simplified NP-complete graph problems

Cited in

(3)

• Variable neighborhood search for edge-ratio network clustering
• A general view on computing communities
• NP-completeness for minimizing maximum edge length in grid embeddings

This page was built for publication: Maximizing edge-ratio is NP-complete

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