Fixed-parameter algorithms for cluster vertex deletion
From MaRDI portal
Publication:987386
DOI10.1007/S00224-008-9150-XzbMATH Open1205.68263OpenAlexW3101793140MaRDI QIDQ987386FDOQ987386
Authors: Falk Hüffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier 
Publication date: 13 August 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-008-9150-x
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Automated generation of search tree algorithms for hard graphs modification problems
- Applying modular decomposition to parameterized cluster editing problems
- Kernels: Annotated, Proper and Induced
- Finding odd cycle transversals.
- The node-deletion problem for hereditary properties is NP-complete
- Faster Scaling Algorithms for Network Problems
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- On efficient fixed-parameter algorithms for weighted vertex cover
- Improved Parameterized Upper Bounds for Vertex Cover
- Aggregating inconsistent information
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Cluster graph modification problems
- A More Effective Linear Kernelization for Cluster Editing
- A general method to speed up fixed-parameter-tractable algorithms
- An approximation algorithm for feedback vertex sets in tournaments
- Kernelization Algorithms for d-Hitting Set Problems
- Correlation clustering with a fixed number of clusters
- The Cluster Editing Problem: Implementations and Experiments
- Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
- Efficient Parameterized Preprocessing for Cluster Editing
- Graph-modeled data clustering: Exact algorithms for clique generation
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
- Parameterized Algorithms for Hitting Set: The Weighted Case
- Going Weighted: Parameterized Algorithms for Cluster Editing
- Algorithms and experiments for parameterized approaches to hard graph problems
- Iterative Compression and Exact Algorithms
- The disjoint cliques problem
Cited In (56)
- Orientable burning number of graphs
- Structural parameterizations of vertex integrity (best paper)
- Parameterized algorithms for cluster vertex deletion on degree-4 graphs and general graphs
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
- Structural parameterizations of vertex integrity
- Learning driven three-phase search for the maximum independent union of cliques problem
- A fast branching algorithm for cluster vertex deletion
- Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
- Title not available (Why is that?)
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- Dominator coloring and CD coloring in almost cluster graphs
- Algorithms for 2-club cluster deletion problems using automated generation of branching rules
- On Making Directed Graphs Transitive
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Fixed-Parameter Algorithms for Graph-Modeled Date Clustering
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
- Algorithms and complexity of \(s\)-club cluster vertex deletion
- On making directed graphs transitive
- Parameterized algorithms for min-max 2-cluster editing
- A tight approximation algorithm for the cluster vertex deletion problem
- A tight approximation algorithm for the cluster vertex deletion problem
- A polynomial kernel for 3-leaf power deletion
- Constant thresholds can make target set selection tractable
- Reducing rank of the adjacency matrix by graph modification
- An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- On 2-clubs in graph-based data clustering: theory and algorithm engineering
- On 2-clubs in graph-based data clustering: theory and algorithm engineering
- Fixed-parameter tractable distances to sparse graph classes
- Even faster parameterized cluster deletion and cluster editing
- Polyhedral properties of the induced cluster subgraphs
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- The maximum independent union of cliques problem: complexity and exact approaches
- A golden ratio parameterized algorithm for cluster editing
- Recognizing map graphs of bounded treewidth
- Alternative parameterizations for cluster editing
- Faster parameterized algorithm for cluster vertex deletion
- Fixed-Parameter Algorithms for Cluster Vertex Deletion
- An FPT algorithm for the vertex cover \(P_4\) problem
- Confronting intractability via parameters
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
- Asymptotic bounds for clustering problems in random graphs
- Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
- Cluster vertex deletion: a parameterization between vertex cover and clique-width
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Reducing rank of the adjacency matrix by graph modification
- Towards optimal and expressive kernelization for \(d\)-hitting set
- Kernelization through Tidying
- Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
- A fast branching algorithm for cluster vertex deletion
- An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem
- The firefighter problem: further steps in understanding its complexity
This page was built for publication: Fixed-parameter algorithms for cluster vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987386)
