Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs

DOI10.1016/J.IPL.2010.05.011MaRDI QIDQ765501zbMATH OpenOpenAlexFDO

Authors Jonathan Backer, J. Mark Keil

Publication date 19 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.05.011

zbMATH Keywords

densest subgraphapproximation algorithmsproper interval graphbipartite permutation graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42)

Recommendations

• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• PTAS for Densest k-Subgraph in Interval Graphs
• PTAS for densest \(k\)-subgraph in interval graphs
• Densest \(k\)-subgraph approximation on intersection graphs
• The densest \(k\)-subgraph problem on clique graphs

Cites work

• scientific article; zbMATH DE number 26490 (Why is no real title available?)
• scientific article; zbMATH DE number 3307459 (Why is no real title available?)
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Clustering and domination in perfect graphs
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Modular decomposition and transitive orientation
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Simple linear time recognition of unit interval graphs

Cited in

(8)

• PTAS for densest \(k\)-subgraph in interval graphs
• PTAS for Densest k-Subgraph in Interval Graphs
• On the \(k\)-edge-incident subgraph problem and its variants
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• Densest \(k\)-subgraph approximation on intersection graphs
• Approximating the sparsest \(k\)-subgraph in chordal graphs
• Proportionally dense subgraph of maximum size: complexity and approximation
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem

This page was built for publication: Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs

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