Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs

DOI10.1007/S00224-014-9568-2zbMath1336.68150MaRDI QIDQ260267

Rodolphe Giroudeau, Marin Bougeret, Rémi Watrigant

Publication date: 21 March 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmchordal graphssparsest \(k\)-subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Well-partitioned chordal graphs

Cites Work

• Unnamed Item
• The \textsc{max quasi-independent set} problem
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• Clustering and domination in perfect graphs
• \(k\)-edge subgraph problems
• Incidence matrices and interval graphs
• The maximum vertex coverage problem on bipartite graphs
• Parameterized complexity of Vertex Cover variants
• Detecting high log-densities
• Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width
• Densest k-Subgraph Approximation on Intersection Graphs
• Approximating the Sparsest k-Subgraph in Chordal Graphs
• Minconvex Factors of Prescribed Size in Graphs
• PTAS for Densest k-Subgraph in Interval Graphs
• Improved Upper Bounds for Partial Vertex Cover

This page was built for publication: Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs