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

DOI10.1016/J.IPL.2010.05.011zbMATH Open1233.05188OpenAlexW2063494850MaRDI QIDQ765501FDOQ765501

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

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

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)

Cites Work

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

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)