Isolation concepts for efficiently enumerating dense subgraphs

DOI10.1016/j.tcs.2009.04.021zbMath1171.68030OpenAlexW2145204415MaRDI QIDQ837155

Falk Hüffner, Christian Komusiewicz, 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

zbMATH Keywords

cliqueexact algorithmNP-hard problemfixed-parameter tractabilityparameterized complexity\(s\)-plex

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On the parameterized complexity of maximum degree contraction problem, Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, Parameterizing edge modification problems above lower bounds, On a generalization of Nemhauser and Trotter's local optimization theorem, A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes, Finding connected secluded subgraphs, Computing dense and sparse subgraphs of weakly closed graphs, Unnamed Item, A generalization of Nemhauser and Trotter's local optimization theorem, On structural parameterizations of the bounded-degree vertex deletion problem, Multivariate algorithmics for finding cohesive subnetworks, Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, Fixed-parameter algorithms for Vertex Cover \(P_3\), On the Parameterized Complexity of Maximum Degree Contraction 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\)\textsf{-Complete Subgraph} problem, Unnamed Item, A classification for community discovery methods in complex networks, Linear-time algorithm for generating c-isolated bicliques, On bounded-degree vertex deletion parameterized by treewidth, Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalization of Nemhauser and Trotter's local optimization theorem
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• The worst-case time complexity for generating all maximal cliques and computational experiments
• The node-deletion problem for hereditary properties is NP-complete
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Parametrized complexity theory.
• Clique-detection models in computational biochemistry and genomics
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• Novel approaches for analyzing biological networks
• Enumeration of isolated cliques and pseudo-cliques
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Measure and conquer
• Isolation Concepts for Enumerating Dense Subgraphs
• Algorithms for maximum independent sets
• A graph‐theoretic generalization of the clique concept
• Algorithms – ESA 2005
• Enumerating Isolated Cliques in Synthetic and Financial Networks
• Network Analysis