Proportionally dense subgraph of maximum size: complexity and approximation
From MaRDI portal
Publication:2334039
DOI10.1016/j.dam.2019.07.010zbMath1426.05084arXiv1903.06579OpenAlexW2929413184WikidataQ127446729 ScholiaQ127446729MaRDI QIDQ2334039
Cristina Bazgan, Janka Chlebíková, Thomas Pontoizeau, Clément Dallard
Publication date: 6 November 2019
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.06579
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)
Related Items
Cites Work
- Unnamed Item
- A general view on computing communities
- Defensive \(k\)-alliances in graphs
- Complexity of finding dense subgraphs
- Structural and algorithmic properties of 2-community structures
- Graphs without a partition into two proportionally dense subgraphs
- Complexity of approximating bounded variants of optimization problems
- Finding Dense Subgraphs with Size Bounds
- On Finding Dense Subgraphs
- Almost all cubic graphs are Hamiltonian
- Reducibility among Combinatorial Problems
- The dense \(k\)-subgraph problem