Isolation concepts for efficiently enumerating dense subgraphs
type: Item
instance of: scholarly article
title: Isolation concepts for efficiently enumerating dense subgraphs
zbMATH Open document ID: 1171.68030
author: Christian Komusiewicz
author: Falk Hüffner
author: Hannes Moser
author: Rolf Niedermeier
published in: Theoretical Computer Science
publication date: 2009-09-10T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5602726
zbMATH Keywords: NP-hard problem
zbMATH Keywords: parameterized complexity
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: exact algorithm
zbMATH Keywords: clique
zbMATH Keywords: \(s\)-plex
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.04.021
OpenAlex ID: W2145204415
cites work: Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
cites work: Novel approaches for analyzing biological networks
cites work: Clique-detection models in computational biochemistry and genomics
cites work: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
cites work: Q4393480
cites work: A generalization of Nemhauser and Trotter's local optimization theorem
cites work: Parametrized complexity theory.
cites work: Measure and conquer
cites work: Q4198056
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Enumerating Isolated Cliques in Synthetic and Financial Networks
cites work: Enumeration of isolated cliques and pseudo-cliques
cites work: Algorithms – ESA 2005
cites work: Isolation Concepts for Enumerating Dense Subgraphs
cites work: Network Analysis
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Q5710169
cites work: Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
cites work: Algorithms for maximum independent sets
cites work: A graph‐theoretic generalization of the clique concept
cites work: The worst-case time complexity for generating all maximal cliques and computational experiments
DOI: 10.1016/J.TCS.2009.04.021
Recommended article: Isolation Concepts for Enumerating Dense Subgraphs
Recommended article: On Finding Dense Subgraphs
Recommended article: Finding Dense Subgraphs with Size Bounds
Recommended article: Complexity of finding dense subgraphs
Recommended article: Finding dense subgraphs
Recommended article: Finding Dense Subgraphs of Sparse Graphs
Recommended article: In search of the densest subgraph
Recommended article: Isolating highly connected induced subgraphs
Recommended article: Isolation concepts for clique enumeration: comparison and computational experiments
description: scientific article; zbMATH DE number 5602726