Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem

DOI10.1016/J.EJOR.2017.04.034MaRDI QIDQ1683124zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

combinatorial optimizationdense subgraphsexact and parameterized algorithmssuperpolynomial approximation algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

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.

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• A measure \& conquer approach for the analysis of exact algorithms
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Approximation of the quadratic knapsack problem
• Approximation of the quadratic knapsack problem
• Clustering and domination in perfect graphs
• Combining Two Worlds: Parameterised Approximation for Vertex Cover
• Complexity of finding dense subgraphs
• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Exact algorithms for problems related to the densest \(k\)-set problem
• Exact and approximate bandwidth
• Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
• Exponential-time approximation of weighted set cover
• Fast algorithms for max independent set
• Fast algorithms for min independent dominating set
• Finding Dense Subgraphs with Size Bounds
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Improved approximation algorithms for maximum graph partitioning problems
• Improved upper bounds for vertex cover
• Inclusion/Exclusion Meets Measure and Conquer
• On Finding Dense Subgraphs
• PTAS for densest \(k\)-subgraph in interval graphs
• Parameterized Approximation Problems
• Paths, Stars and the Number Three
• Pathwidth of cubic graphs and exact algorithms
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Quadratic knapsack problems
• Reducibility among combinatorial problems
• Set partitioning via inclusion-exclusion
• The \textsc{max quasi-independent set} problem
• The dense \(k\)-subgraph problem
• The quadratic 0-1 knapsack problem with series-parallel support

Cited in

(13)

• The densest \(k\)-subgraph problem on clique graphs
• Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
• Complexity and approximability of the happy set problem
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity
• On solving the densest \(k\)-subgraph problem on large graphs
• The densest \(k\)-subhypergraph problem
• The dense \(k\)-subgraph problem
• A note on the approximability of the dense subgraph problem.
• Computing densest \(k\)-subgraph with structural parameters
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Graph classes and approximability of the happy set problem
• 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)