Approximating the Sparsest k-Subgraph in Chordal Graphs

DOI10.1007/978-3-319-08001-7_7zbMath1416.68141OpenAlexW31735291MaRDI QIDQ3188867

Rodolphe Giroudeau, Rémi Watrigant, Marin Bougeret

Publication date: 2 September 2014

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-08001-7_7

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (3)

Provable randomized rounding for minimum-similarity diversification ⋮ Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs ⋮ PTAS for densest \(k\)-subgraph in interval graphs

This page was built for publication: Approximating the Sparsest k-Subgraph in Chordal Graphs