Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs
Authors:
- Jonathan BackerJBJonathan Backer
- J. Mark KeilJKJ. Mark Keil
- 1 July 2010
- journal article
- research article
- Published by Elsevier in Information Processing Letters
- Vol. 110 (16) , 635-638
Abstract
No abstract availableFunding Information
- Natural Sciences and Engineering Research Council of Canada
- Natural Sciences and Engineering Research Council of Canada
This publication has 8 references indexed in Scilit:
- Detecting high log-densities2010
- A constant approximation algorithm for the densest k-subgraph problem on chordal graphsInformation Processing Letters, 2008
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite CliqueSIAM Journal on Computing, 2006
- Modular decomposition and transitive orientationDiscrete Mathematics, 1999
- Simple linear time recognition of unit interval graphsInformation Processing Letters, 1995
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- Approximation schemes for covering and packing problems in image processing and VLSIJournal of the ACM, 1985
- Clustering and domination in perfect graphsDiscrete Applied Mathematics, 1984