PTAS for Densest k-Subgraph in Interval Graphs

DOI10.1007/978-3-642-22300-6_53MaRDI QIDQ5199279zbMATH OpenOpenAlexFDO

Authors Tim Nonner

Publication date 12 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22300-6_53

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• PTAS for densest \(k\)-subgraph in interval graphs
• Densest k-subgraph approximation on intersection graphs
• Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem
• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• The densest k-subhypergraph problem
• The densest \(k\)-subhypergraph problem
• On Finding Dense Subgraphs

Cited in

(9)

• Finding connected \(k\)-subgraphs with high density
• The densest \(k\)-subgraph problem on clique graphs
• On the \(k\)-edge-incident subgraph problem and its variants
• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• PTAS for densest \(k\)-subgraph in interval graphs
• Densest k-subgraph approximation on intersection graphs
• Approximating the sparsest k-subgraph in chordal graphs
• Approximation algorithm for the minimum interval partial multi-cover problem
• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs

This page was built for publication: PTAS for Densest k-Subgraph in Interval Graphs

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