Proportionally dense subgraph of maximum size: complexity and approximation

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

zbMATH Keywords

complexityapproximationdense subgraphHamiltonian cubic graphs

Mathematics Subject Classification ID

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

Graphs without a partition into two proportionally dense subgraphs

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