CONSTRUCTING THE HIGHEST DEGREE SUBGRAPH FOR DENSE GRAPHS IS IN NLAP

Authors
ANDREEV AE CLEMENTI AEF ROLIM JDP
Citation
Ae. Andreev et al., CONSTRUCTING THE HIGHEST DEGREE SUBGRAPH FOR DENSE GRAPHS IS IN NLAP, Theoretical computer science, 161(1-2), 1996, pp. 307-314
Citations number
11
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
161
Issue
1-2
Year of publication
1996
Pages
307 - 314
Database
ISI
SICI code
0304-3975(1996)161:1-2<307:CTHDSF>2.0.ZU;2-1
Abstract
in this paper, we first show that the Highest Degree Subgraph problem remains P-complete for dense graphs (i.e. when m = Omega(n(2)/poly log n)). This hardness result gives a clear motivation in studying the ap proximability of the Highest Degree Problem even for this restricted c ase. We then provide an NC-approximation scheme computing approximate solutions for dense graphs, thus proving that, in this case, the probl em belongs to the N C A S class.