Computing densest k-subgraph with structural parameters
From MaRDI portal
Publication:2680362
Recommendations
- Finding dense subgraphs of sparse graphs
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- The dense \(k\)-subgraph problem
Cites work
- A fast branching algorithm for cluster vertex deletion
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- Algorithmic meta-theorems for restrictions of treewidth
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Approximating clique-width and branch-width
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Approximating rank-width and clique-width quickly
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Clustering and domination in perfect graphs
- Depth-First Search and Linear Graph Algorithms
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Finding Branch-Decompositions and Rank-Decompositions
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 6515825 (Why is no real title available?)
- scientific article; zbMATH DE number 6515828 (Why is no real title available?)
- scientific article; zbMATH DE number 1342117 (Why is no real title available?)
- Linear time solvable optimization problems on graphs of bounded clique-width
- Modular decomposition and transitive orientation
- On the clique-width of some perfect graph classes
- Parameterized algorithms
- Parameterized Algorithms for Modular-Width
- Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
- Parameterized complexity of Vertex Cover variants
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- The dense \(k\)-subgraph problem
- The hardness of approximation: Gap location
- The maximum vertex coverage problem on bipartite graphs
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Upper bounds to the clique width of graphs
Cited in
(5)- Computing the \(k\) densest subgraphs of a graph
- Finding dense subgraphs of sparse graphs
- Discounted average degree density metric and new algorithms for the densest subgraph problem
- scientific article; zbMATH DE number 7765378 (Why is no real title available?)
- Fixed-parameter algorithms for cardinality-constrained graph partitioning problems on sparse graphs
This page was built for publication: Computing densest \(k\)-subgraph with structural parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2680362)
