Finding dense subgraphs

DOI10.1007/BFB0015413MaRDI QIDQ6487951zbMATH OpenFDO

Authors Yuichi Asahiro, Kazuo Iwama

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/BFB0015413

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Complexity of finding dense subgraphs
• On Finding Dense Subgraphs
• Finding dense subgraphs of sparse graphs
• The dense \(k\)-subgraph problem
• Determination of the densest subgraph

Cites work

• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• On the Complexity of Timetable and Multicommodity Flow Problems
• Reducibility among combinatorial problems
• Some simplified NP-complete graph problems
• The complexity of theorem-proving procedures

Cited in

(20)

• Complexity of finding dense subgraphs
• Proportionally dense subgraph of maximum size: complexity and approximation
• Finding connected \(k\)-subgraphs with high density
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• The complexity of detecting fixed-density clusters
• Determination of the densest subgraph
• Finding Connected Dense k-Subgraphs
• Sandwiching a densest subgraph by consecutive cores
• Finding dense subgraphs in \(G(n,1/2)\)
• On Finding Dense Subgraphs
• A decomposition of a graph into dense subgraphs
• ETH hardness for densest-k-subgraph with perfect completeness
• Finding dense subgraphs of sparse graphs
• Dense Induced Subgraphs of Dense Bipartite Graphs
• Greedily finding a dense subgraph
• The dense \(k\)-subgraph problem
• Solving the multiobjective quasi-clique problem
• Dense and sparse graph partition
• Ensuring connectedness for the maximum quasi-clique and densest k-subgraph problems
• Isolation concepts for efficiently enumerating dense subgraphs

This page was built for publication: Finding dense subgraphs

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