Structural and algorithmic properties of 2-community structures

DOI10.1007/s00453-017-0283-7zbMath1388.05149OpenAlexW2587632246WikidataQ59603515 ScholiaQ59603515MaRDI QIDQ1635716

Cristina Bazgan, Thomas Pontoizeau, Janka Chlebíková

Publication date: 1 June 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0283-7

zbMATH Keywords

complexityclusteringsocial networksgraph partitioningcommunity structure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Graphs without a partition into two proportionally dense subgraphs, Proportionally dense subgraph of maximum size: complexity and approximation

Cites Work

• Graph clustering
• A general view on computing communities
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Unfriendly partitions of a graph
• Balanced graph partitioning
• Approximation of satisfactory bisection problems
• Satisfactory graph partition, variants, and generalizations
• Balanced partitions of trees and applications
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• The satisfactory partition problem
• Unnamed Item
• Unnamed Item