Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
DOI10.1016/J.EJOR.2017.04.034zbMATH Open1375.90296OpenAlexW2606334169MaRDI QIDQ1683124FDOQ1683124
Authors: Nicolas Bourgeois, A. Giannakos, G. Lucarelli, Ioannis Milis, Vangelis Th. Paschos 
Publication date: 6 December 2017
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2017.04.034
Recommendations
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- The dense \(k\)-subgraph problem
- On solving the densest \(k\)-subgraph problem on large graphs
- Algorithms for the densest subgraph with at least \(k\) vertices and with a specified subset
- The densest \(k\)-subhypergraph problem
- The densest \(k\)-subhypergraph problem
- Densest \(k\)-subgraph approximation on intersection graphs
- A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
- A note on the approximability of the dense subgraph problem.
combinatorial optimizationdense subgraphsexact and parameterized algorithmssuperpolynomial approximation algorithms
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Reducibility among combinatorial problems
- A measure \& conquer approach for the analysis of exact algorithms
- Clustering and domination in perfect graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- PTAS for densest \(k\)-subgraph in interval graphs
- Approximation algorithms for maximization problems arising in graph partitioning
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Parameterized Approximation Problems
- On Finding Dense Subgraphs
- The \textsc{max quasi-independent set} problem
- Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
- Title not available (Why is that?)
- The dense \(k\)-subgraph problem
- Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
- Improved approximation algorithms for maximum graph partitioning problems
- A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
- Complexity of finding dense subgraphs
- Quadratic knapsack problems
- Title not available (Why is that?)
- Improved upper bounds for vertex cover
- Fast algorithms for max independent set
- Set partitioning via inclusion-exclusion
- Paths, Stars and the Number Three
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- The quadratic 0-1 knapsack problem with series-parallel support
- Fast algorithms for min independent dominating set
- Pathwidth of cubic graphs and exact algorithms
- Exact and approximate bandwidth
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Inclusion/Exclusion Meets Measure and Conquer
- Finding Dense Subgraphs with Size Bounds
- Approximation of the quadratic knapsack problem
- Approximation of the quadratic knapsack problem
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Exact algorithms for problems related to the densest \(k\)-set problem
Cited In (13)
- Computing densest \(k\)-subgraph with structural parameters
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- The dense \(k\)-subgraph problem
- A note on the approximability of the dense subgraph problem.
- The densest \(k\)-subhypergraph problem
- Graph classes and approximability of the happy set problem
- Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity
- Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- The densest \(k\)-subgraph problem on clique graphs
- Complexity and approximability of the happy set problem
- On solving the densest \(k\)-subgraph problem on large graphs
- Exact algorithms for problems related to the densest \(k\)-set problem
This page was built for publication: Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1683124)
