Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
From MaRDI portal
Publication:1683124
DOI10.1016/j.ejor.2017.04.034zbMath1375.90296OpenAlexW2606334169MaRDI QIDQ1683124
Vangelis Th. Paschos, Giorgio Lucarelli, Ioannis Milis, Nicolas Bourgeois, Aristotelis Giannakos
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
combinatorial optimizationdense subgraphsexact and parameterized algorithmssuperpolynomial approximation algorithms
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Complexity and approximability of the happy set problem, Computing densest \(k\)-subgraph with structural parameters, Graph classes and approximability of the happy set problem, On solving the densestk-subgraph problem on large graphs
Cites Work
- Unnamed Item
- Unnamed Item
- PTAS for densest \(k\)-subgraph in interval graphs
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- The \textsc{max quasi-independent set} problem
- Exact and approximate bandwidth
- Improved upper bounds for vertex cover
- 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
- Exponential-time approximation of weighted set cover
- Pathwidth of cubic graphs and exact algorithms
- Clustering and domination in perfect graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Complexity of finding dense subgraphs
- Approximation of the quadratic knapsack problem
- The quadratic 0-1 knapsack problem with series-parallel support
- Fast algorithms for min independent dominating set
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- Fast algorithms for max independent set
- Exact algorithms for problems related to the densest \(k\)-set problem
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Detecting high log-densities
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- Approximation of the Quadratic Knapsack Problem
- A measure & conquer approach for the analysis of exact algorithms
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Parameterized Approximation Problems
- Set Partitioning via Inclusion-Exclusion
- Finding Dense Subgraphs with Size Bounds
- On Finding Dense Subgraphs
- Inclusion/Exclusion Meets Measure and Conquer
- Quadratic knapsack problems
- Paths, Stars and the Number Three
- Exact and Approximation Algorithms for Densest k-Subgraph
- Reducibility among Combinatorial Problems
- The dense \(k\)-subgraph problem
