The parameterised complexity of computing the maximum modularity of a graph

DOI10.1007/S00453-019-00649-7MaRDI QIDQ786031zbMATH OpenOpenAlexWikidataFDO

Authors Kitty Meeks, Fiona Skerman

Publication date 12 August 2020

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

community detectioninteger quadratic programmingmodularitypathwidthvertex cover

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7378595
• Maximum modular graphs
• On Finding Graph Clusterings with Maximum Modularity
• Modular-width: an auxiliary parameter for parameterized parallel complexity
• Parameterized Algorithms for Modular-Width

Cites work

• A linear time algorithm for finding tree-decompositions of small treewidth
• Additive approximation algorithms for modularity maximization
• Communities in Networks
• Fast unfolding of communities in large networks
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 5725105 (Why is no real title available?)
• Modularity in several random graph models
• Modularity of Erdős-Rényi random graphs
• Modularity of Erdős-Rényi random graphs
• Modularity of regular and treelike graphs
• On the complexity of Newman's community finding approach for biological and social networks
• Parameterized algorithms
• Treewidth. Computations and approximations
• What makes equitable connected partition easy

Cited in

(11)

• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• The complexity of modular graph automorphism
• scientific article; zbMATH DE number 1136076 (Why is no real title available?)
• Modular-width: an auxiliary parameter for parameterized parallel complexity
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)
• Grundy Distinguishes Treewidth from Pathwidth
• Grundy distinguishes treewidth from pathwidth
• Maximum modular graphs
• Modularity and graph expansion
• Equitable connected partition and structural parameters revisited: N-fold beats Lenstra
• Modularity clustering parameterized by max leaf number

Describes a project that uses

Uses Software

• GenLouvain

This page was built for publication: The parameterised complexity of computing the maximum modularity of a graph

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