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

DOI10.1016/j.ipl.2010.05.011zbMath1233.05188OpenAlexW2063494850MaRDI QIDQ765501

J. Mark Keil, Jonathan Backer

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

approximation algorithmsproper interval graphbipartite permutation graphdensest subgraph

Mathematics Subject Classification ID

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

Related Items (3)

Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ PTAS for densest \(k\)-subgraph in interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Simple linear time recognition of unit interval graphs
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• Clustering and domination in perfect graphs
• Modular decomposition and transitive orientation
• Detecting high log-densities
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation algorithms for NP-complete problems on planar graphs
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

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