Proportionally dense subgraphs: parameterized hardness and efficiently solvable cases

DOI10.1007/978-981-96-2845-2_2MaRDI QIDQ6996807zbMATH OpenFDO

Authors Narmina Baghirova, Antoine Castillon

Publication date 15 April 2025

Full work available at URL https://doi.org/10.1007/978-981-96-2845-2_2

zbMATH Keywords

algorithmscommunitiescomplexitydense subgraphparameterized complexitytreewidth

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A general view on computing communities
• A new approach on locally checkable problems
• Finding \(k\)-community structures in special graph classes
• Graphs without a partition into two proportionally dense subgraphs
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Locally checkable problems parameterized by clique-width
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Multivariate algorithmics for finding cohesive subnetworks
• Parameterized complexity of satisfactory partition problem
• Proportionally dense subgraph of maximum size: complexity and approximation
• Some simplified NP-complete graph problems
• Structural and algorithmic properties of 2-community structures
• The dense \(k\)-subgraph problem
• The satisfactory partition problem
• Treewidth. Computations and approximations

This page was built for publication: Proportionally dense subgraphs: parameterized hardness and efficiently solvable cases

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