The parameterised complexity of computing the maximum modularity of a graph

DOI10.1007/s00453-019-00649-7zbMath1452.68091OpenAlexW2963890422WikidataQ126864762 ScholiaQ126864762MaRDI QIDQ786031

Kitty Meeks, Fiona Skerman

Publication date: 12 August 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00649-7

zbMATH Keywords

pathwidthmodularityvertex covercommunity detectioninteger quadratic programming

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Grundy Distinguishes Treewidth from Pathwidth, Unnamed Item

Uses Software

• GenLouvain

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Treewidth. Computations and approximations
• Modularity in several random graph models
• On the complexity of Newman's community finding approach for biological and social networks
• Modularity of regular and treelike graphs
• Communities in Networks
• What Makes Equitable Connected Partition Easy
• Additive Approximation Algorithms for Modularity Maximization
• Modularity of Erdős‐Rényi random graphs
• Fast unfolding of communities in large networks
• A linear time algorithm for finding tree-decompositions of small treewidth
• Parameterized Algorithms