Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs

DOI10.1007/978-3-319-04298-5_14MaRDI QIDQ2938098zbMATH OpenOpenAlexFDO

Authors Marin Bougeret, Rodolphe Giroudeau, Rémi Watrigant, Nicolas Bousquet

Publication date 13 January 2015

Published in SOFSEM 2014: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-04298-5_14

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• scientific article; zbMATH DE number 7651188
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• Subgraph sparsification and nearly optimal ultrasparsifiers
• Parameterized dominating set problem in chordal graphs: Complexity and lower bound
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Parameterized complexity of set-restricted disjoint paths on chordal graphs
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs

Cited in

(8)

• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• An efficient algorithm for enumerating chordal bipartite induced subgraphs in sparse graphs
• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• Computing densest \(k\)-subgraph with structural parameters
• Largest Chordal and Interval Subgraphs Faster Than 2 n
• Approximating the sparsest k-subgraph in chordal graphs
• Linear-time generation of random chordal graphs
• On solving the densest \(k\)-subgraph problem on large graphs

This page was built for publication: Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938098)