Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion

DOI10.1007/s00453-011-9492-7zbMath1236.68100OpenAlexW2122043221MaRDI QIDQ2429325

Hannes Moser, René van Bevern, Rolf Niedermeier

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9492-7

zbMATH Keywords

fixed-parameter tractabilitypolynomial-time data reductionNP-hard graph problemcomputational intractabilitygraph-based data clustering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (22)

Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space ⋮ Parameterized complexity of Eulerian deletion problems ⋮ Towards optimal and expressive kernelization for \(d\)-hitting set ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Kernels for packing and covering problems ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Unnamed Item ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size ⋮ On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments ⋮ An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem

Cites Work

• Unnamed Item
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Graph-based data clustering with overlaps
• Graph clustering
• Finding odd cycle transversals.
• Parameterized graph cleaning problems
• Fixed-parameter algorithms for cluster vertex deletion
• A kernelization algorithm for \(d\)-hitting set
• On problems without polynomial kernels
• The node-deletion problem for hereditary properties is NP-complete
• Logical definability of NP optimization problems
• Cluster graph modification problems
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Incompressibility through Colors and IDs
• A graph‐theoretic definition of a sociometric clique†
• A graph‐theoretic generalization of the clique concept
• Fast FPT-Algorithms for Cleaning Grids

This page was built for publication: Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion