Parameterizing edge modification problems above lower bounds
type: Item
instance of: scholarly article
title: Parameterizing edge modification problems above lower bounds
title: Parameterizing Edge Modification Problems Above Lower Bounds
zbMATH Open document ID: 1386.68075
zbMATH Open document ID: 1386.68074
DOI: 10.1007/978-3-319-34171-2_5
DOI: 10.1007/S00224-016-9746-5
author: René van Bevern
author: Vincent Froese
author: Christian Komusiewicz
published in: Theory of Computing Systems
published in: Computer Science – Theory and Applications
publication date: 2018-06-01T00:00:00Z
publication date: 2016-07-25T00:00:00Z
full work available at URL: https://arxiv.org/abs/1512.04047
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6879948
zbMATH DE Number: 6605919
zbMATH Keywords: NP-hard problem
zbMATH Keywords: fixed-parameter algorithm
zbMATH Keywords: subgraph packing
zbMATH Keywords: kernelization
zbMATH Keywords: graph-based clustering
zbMATH Keywords: feedback arc set
zbMATH Keywords: cluster editing
MaRDI profile type: Publication
OpenAlex ID: W2578359728
OpenAlex ID: W2253466184
arXiv ID: 1512.04047
cites work: Ranking Tournaments
cites work: Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
cites work: Kernels for feedback arc set in tournaments
cites work: Towards optimal and expressive kernelization for \(d\)-hitting set
cites work: A golden ratio parameterized algorithm for cluster editing
cites work: Going weighted: parameterized algorithms for cluster editing
cites work: On generating triangle-free graphs
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: A \(2k\) kernel for the cluster editing problem
cites work: Parameterized Algorithms
cites work: On Multiway Cut Parameterized above Lower Bounds
cites work: Fundamentals of parameterized complexity
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
cites work: Automated generation of search tree algorithms for hard graphs modification problems
cites work: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
cites work: Cluster editing with locally bounded modifications
cites work: NP-hard problems in hierarchical-tree clustering
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Faster Parameterized Algorithms Using Linear Programming
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
cites work: Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem
cites work: Almost 2-SAT is fixed-parameter tractable
cites work: Cluster graph modification problems
cites work: Edge-Deletion Problems
cites work: Fast FAST
cites work: Incompressibility of \(H\)-free edge modification problems
cites work: Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
cites work: Exploring the subexponential complexity of completion problems
cites work: Graph-based data clustering with overlaps
cites work: Exact exponential algorithms.
cites work: Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
cites work: Tight bounds for parameterized complexity of Cluster Editing
cites work: On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
cites work: A more effective linear kernelization for cluster editing
cites work: Isolation concepts for efficiently enumerating dense subgraphs
cites work: Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
cites work: Q4967164
cites work: Two Edge Modification Problems without Polynomial Kernels
cites work: Complexity and parameterized algorithms for cograph editing
cites work: Q5710169
cites work: Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
cites work: Applying modular decomposition to parameterized cluster editing problems
cites work: Parameterized algorithms for feedback set problems and their duals in tournaments
cites work: Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
description: scientific article; zbMATH DE number 6605919

Parameterizing edge modification problems above lower bounds (cites work)
cites work: Parameterizing edge modification problems above lower bounds