Graphs without a partition into two proportionally dense subgraphs

DOI10.1016/j.ipl.2019.105877zbMath1481.05124arXiv1806.10963OpenAlexW2985129618MaRDI QIDQ2281161

Cristina Bazgan, Clément Dallard, Janka Chlebíková

Publication date: 19 December 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1806.10963

zbMATH Keywords

combinatorial problemsdense subgraphgraph partition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Density (toughness, etc.) (05C42)

Related Items (1)

Proportionally dense subgraph of maximum size: complexity and approximation

Cites Work

• A general view on computing communities
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Complexity of finding dense subgraphs
• Structural and algorithmic properties of 2-community structures
• Proportionally dense subgraph of maximum size: complexity and approximation
• The satisfactory partition problem
• On Finding Dense Subgraphs
• The dense \(k\)-subgraph problem

This page was built for publication: Graphs without a partition into two proportionally dense subgraphs