The densest k-subgraph problem on clique graphs

Maria Liazi (), Ioannis Milis (), Fanny Pascual () and Vassilis Zissimopoulos ()
Additional contact information
Maria Liazi: University of Athens
Ioannis Milis: Athens University Economics and Business
Fanny Pascual: University of Évry
Vassilis Zissimopoulos: University of Athens

Journal of Combinatorial Optimization, 2007, vol. 14, issue 4, No 6, 465-474

Abstract: Abstract The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The problem is strongly NP-hard, as a generalization of the well known Clique problem and we also know that it does not admit a Polynomial Time Approximation Scheme (PTAS). In this paper we focus on special cases of the problem, with respect to the class of the input graph. Especially, towards the elucidation of the open questions concerning the complexity of the problem for interval graphs as well as its approximability for chordal graphs, we consider graphs having special clique graphs. We present a PTAS for stars of cliques and a dynamic programming algorithm for trees of cliques.

Keywords: Densest k-subgraph; Clique graph; Polynomial time approximation scheme; Dynamic programming (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9069-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:14:y:2007:i:4:d:10.1007_s10878-007-9069-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9069-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().