Computing densest \(k\)-subgraph with structural parameters

DOI10.1007/s10878-022-00927-1OpenAlexW4312163572MaRDI QIDQ2680362

Tesshu Hanaka

Publication date: 29 December 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2207.09803

zbMATH Keywords

approximation algorithmfixed parameter tractabilitystructural parametersdensest subgraphssparsest subgraphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast branching algorithm for cluster vertex deletion
• Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
• Clustering and domination in perfect graphs
• Modular decomposition and transitive orientation
• The hardness of approximation: Gap location
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• Algorithmic meta-theorems for restrictions of treewidth
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• The maximum vertex coverage problem on bipartite graphs
• Parameterized complexity of Vertex Cover variants
• Approximating clique-width and branch-width
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• Parameterized Algorithms for Modular-Width
• Detecting high log-densities
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximating rank-width and clique-width quickly
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Parameterized Algorithms
• Depth-First Search and Linear Graph Algorithms
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• Finding Branch-Decompositions and Rank-Decompositions
• The dense \(k\)-subgraph problem

This page was built for publication: Computing densest \(k\)-subgraph with structural parameters