Isolation concepts for efficiently enumerating dense subgraphs
DOI10.1016/J.TCS.2009.04.021zbMATH Open1171.68030OpenAlexW2145204415MaRDI QIDQ837155FDOQ837155
Authors: Christian Komusiewicz, Falk Hüffner, Hannes Moser, Rolf Niedermeier 
Publication date: 10 September 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.021
Recommendations
- Isolation Concepts for Enumerating Dense Subgraphs
- On Finding Dense Subgraphs
- Finding Dense Subgraphs with Size Bounds
- Complexity of finding dense subgraphs
- Finding dense subgraphs
- Finding dense subgraphs of sparse graphs
- In search of the densest subgraph
- Isolating highly connected induced subgraphs
- Isolation concepts for clique enumeration: comparison and computational experiments
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)
Cites Work
- Title not available (Why is that?)
- The node-deletion problem for hereditary properties is NP-complete
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Parametrized complexity theory.
- Title not available (Why is that?)
- A generalization of Nemhauser and Trotter's local optimization theorem
- Clique-detection models in computational biochemistry and genomics
- Novel approaches for analyzing biological networks
- Clique relaxations in social network analysis: the maximum \(k\)-plex problem
- Title not available (Why is that?)
- A graph‐theoretic generalization of the clique concept
- Algorithms for maximum independent sets
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Network Analysis
- Measure and conquer
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Algorithms – ESA 2005
- Enumeration of isolated cliques and pseudo-cliques
- Isolation Concepts for Enumerating Dense Subgraphs
- Enumerating Isolated Cliques in Synthetic and Financial Networks
Cited In (27)
- Enumerating Isolated Cliques in Synthetic and Financial Networks
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- A measure and conquer approach for the parameterized bounded degree-one vertex deletion
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Title not available (Why is that?)
- A generalization of Nemhauser and Trotter's local optimization theorem
- Linear-time algorithm for generating c-isolated bicliques
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- An efficient algorithm for solving pseudo clique enumeration problem
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- Cliques with maximum/minimum edge neighborhood and neighborhood density
- Hardness and tractability of the \(\gamma\)-complete subgraph problem
- On structural parameterizations of the bounded-degree vertex deletion problem
- On bounded-degree vertex deletion parameterized by treewidth
- Computing dense and sparse subgraphs of weakly closed graphs
- Enumeration of isolated cliques and pseudo-cliques
- On the parameterized complexity of maximum degree contraction problem
- On the Parameterized Complexity of Maximum Degree Contraction Problem.
- Finding connected secluded subgraphs
- Isolation Concepts for Enumerating Dense Subgraphs
- Finding connected secluded subgraphs
- A classification for community discovery methods in complex networks
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- On structural parameterizations of the bounded-degree vertex deletion problem
- On the parameterized complexity of non-hereditary relaxations of clique
- Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
- Multivariate algorithmics for finding cohesive subnetworks
This page was built for publication: Isolation concepts for efficiently enumerating dense subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q837155)
