Dense and sparse graph partition

DOI10.1016/J.DAM.2012.06.004MaRDI QIDQ714027zbMATH OpenOpenAlexFDO

Authors Julien Darlay, Nadia Brauner, Julien Moncel

Publication date 19 October 2012

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

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

zbMATH Keywords

algorithmscommunity detectioncomplexitygraph partition

Mathematics Subject Classification ID

Connectivity (05C40) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Recommendations

• Determination of the densest subgraph
• Finding dense subgraphs
• On Finding Dense Subgraphs
• Clustering, community partition and disjoint spanning trees
• On the sum-max graph partitioning problem

Cites work

• A faster algorithm for betweenness centrality*
• Clustering on trees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph clustering
• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 2231543 (Why is no real title available?)
• List Partitions
• NP-hardness of Euclidean sum-of-squares clustering
• SOFSEM 2006: Theory and Practice of Computer Science
• The dense \(k\)-subgraph problem

Cited in

(10)

• Parliament seating assignment problems
• Cliques in regular graphs and the core-periphery problem in social networks
• Clustering, community partition and disjoint spanning trees
• Looking for High Density Zones in a Graph
• Partitioning problems in dense hypergraphs
• Dense graph partitioning on sparse and dense graphs
• Maximizing utilitarian and egalitarian welfare of fractional hedonic games on tree-like graphs
• Efficient heuristics to compute minimal and stable feedback arc sets
• Maximizing utilitarian and egalitarian welfare of fractional hedonic games on tree-like graphs
• Dense graph partitioning on sparse and dense graphs

Describes a project that uses

Uses Software

• Graclus

This page was built for publication: Dense and sparse graph partition

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