Maximizing edge-ratio is NP-complete

DOI10.1016/J.DAM.2011.07.016zbMATH Open1408.68069OpenAlexW2055422348MaRDI QIDQ765326FDOQ765326

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

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

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)

Cites Work

• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• On clusterings: good, bad and spectral

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)