Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
From MaRDI portal
Publication:1928521
DOI10.1007/s10878-011-9391-5zbMath1261.90081OpenAlexW2050952499MaRDI QIDQ1928521
Hannes Moser, Manuel Sorge, Rolf Niedermeier
Publication date: 3 January 2013
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-011-9391-5
social network analysisparameterized algorithmicsdense subgraphsNP-complete graph problems\(k\)-dependent sets\(s\)-plexesbiological network analysis
Related Items (20)
Approximating Bounded Degree Deletion via Matroid Matching ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ Parameterizing edge modification problems above lower bounds ⋮ Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ Unnamed Item ⋮ Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Approximating power node-deletion problems ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Fixed-parameter algorithms for Vertex Cover \(P_3\) ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters ⋮ Continuous cubic formulations for cluster detection problems in networks
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial algorithms for the maximum \(k\)-plex problem
- Isolation concepts for efficiently enumerating dense subgraphs
- Fixed-parameter algorithms for cluster vertex deletion
- Isolation concepts for clique enumeration: comparison and computational experiments
- The node-deletion problem for hereditary properties is NP-complete
- A general method to speed up fixed-parameter-tractable algorithms
- A fast algorithm for the maximum clique problem
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Crown structures for vertex cover kernelization
- Parametrized complexity theory.
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Novel approaches for analyzing biological networks
- Enumeration of isolated cliques and pseudo-cliques
- A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- A Linear Kernel for Co-Path/Cycle Packing
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Kernelization: New Upper and Lower Bound Techniques
- Vertex packings: Structural properties and algorithms
- A graph‐theoretic generalization of the clique concept
- Application of an Annealed Neural Network to a Timetabling Problem
- A Generalization of Nemhauser and Trotter's Local Optimization Theorem.
This page was built for publication: Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
