ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness.
Mark BravermanYoung Kun-KoAviad RubinsteinOmri WeinsteinPublished in: CoRR (2015)
Keyphrases
- graph mining
- similarity graph
- dense subgraphs
- np hard
- computational complexity
- graph databases
- frequent subgraphs
- frequent subgraph mining
- phase transition
- worst case
- pattern mining
- data quality
- np complete
- community discovery
- graph data
- link prediction
- functional modules
- data mining
- np hardness
- lower bound
- similarity measure
- feature selection