Finding dense subgraphs of sparse graphs

DOI10.1007/978-3-642-33293-7_23MaRDI QIDQ4899257zbMATH OpenOpenAlexFDO

Authors Christian Komusiewicz, Manuel Sorge

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33293-7_23

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Finding dense subgraphs
• Complexity of finding dense subgraphs
• Finding Dense Subgraphs with Size Bounds
• Computing densest \(k\)-subgraph with structural parameters

Cited in

(25)

• Complexity of finding dense subgraphs
• Improving man-optimal stable matchings by minimum change of preference lists
• The parameterized complexity of the rainbow subgraph problem
• Hardness and tractability of the \(\gamma\)-complete subgraph problem
• Parameterized complexity of immunization in the threshold model
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• The complexity of detecting fixed-density clusters
• Computing densest \(k\)-subgraph with structural parameters
• Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure
• The parameterized complexity of the rainbow subgraph problem
• Finding Connected Dense k-Subgraphs
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Finding Dense Subgraphs with Size Bounds
• ETH hardness for densest-k-subgraph with perfect completeness
• Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
• Greedily finding a dense subgraph
• Test dense subgraphs in sparse uniform hypergraph
• Finding highly connected subgraphs
• Enumerating connected induced subgraphs: improved delay and experimental comparison
• scientific article; zbMATH DE number 7765378 (Why is no real title available?)
• Immunization in the threshold model: a parameterized complexity study
• Finding dense subgraphs
• Isolation concepts for efficiently enumerating dense subgraphs
• A general tractable density concept for graphs

This page was built for publication: Finding dense subgraphs of sparse graphs

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