Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes

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

zbMATH Keywords

social network analysisparameterized algorithmicsdense subgraphsNP-complete graph problems\(k\)-dependent sets\(s\)-plexesbiological network analysis

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

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

• Pajek
• Pajek datasets
• DIMACS

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