Fixed-parameter tractability of graph modification problems for hereditary properties
From MaRDI portal
(Redirected from Publication:1352005)
Recommendations
Cites work
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Complement reducible graphs
- Computing the Minimum Fill-In is NP-Complete
- Generating binary trees by transpositions
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 3286813 (Why is no real title available?)
- Node-and edge-deletion NP-complete problems
- Node-Deletion NP-Complete Problems
- On the complexity of the maximum subgraph problem
Cited in
(only showing first 100 items - show all)- Closest 4-leaf power is fixed-parameter tractable
- Dynamically maintaining split graphs
- Parameterized complexity of finding regular induced subgraphs
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Two edge modification problems without polynomial kernels
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- Vertex deletion problems on chordal graphs
- Reconstructing gene trees from Fitch's xenology relation
- Parameterized complexity of vertex colouring
- Parameterized complexity of finding subgraphs with hereditary properties.
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Proper interval vertex deletion
- Online node- and edge-deletion problems with advice
- Paths to trees and cacti
- On the parameterized complexity of contraction to generalization of trees
- Faster parameterized algorithm for cluster vertex deletion
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- A polynomial kernel for diamond-free editing
- Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
- Structural parameterizations of Tracking Paths problem
- (Sub)linear kernels for edge modification problems toward structured graph classes
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Faster FPT algorithms for deletion to pairs of graph classes
- Streaming deletion problems parameterized by vertex cover
- Vertex deletion into bipartite permutation graphs
- Distance from triviality 2.0: hybrid parameterizations
- Parameterized aspects of strong subgraph closure
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- Edge deletion problems: branching facilitated by modular decomposition
- Minimum fill-in of sparse graphs: kernelization and approximation
- Clustering with partial information
- Applying modular decomposition to parameterized cluster editing problems
- Kernels for packing and covering problems
- Complexity of modification problems for reciprocal best match graphs
- Faster algorithms for cograph edge modification problems
- Tractability of König edge deletion problems
- A completeness theory for polynomial (Turing) kernelization
- Modifying a graph using vertex elimination
- Faster parameterized algorithms for deletion to split graphs
- An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
- Parameterized complexity of the induced subgraph problem in directed graphs
- Additive approximation for edge-deletion problems
- Polynomial kernelization for removing induced claws and diamonds
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Editing to a connected graph of given degrees
- On the complexity of multi-parameterized cluster editing
- Fixed-parameter tractable distances to sparse graph classes
- Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Obtaining a planar graph by vertex deletion
- Parameterized complexity of Eulerian deletion problems
- Searching for better fill-in
- On the interval completion of chordal graphs
- A fast branching algorithm for cluster vertex deletion
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Parameterized enumeration for modification problems
- Polynomial kernelization for removing induced claws and diamonds
- Exploring the subexponential complexity of completion problems
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- The Multi-parameterized Cluster Editing Problem
- Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
- The birth and early years of parameterized complexity
- A basic parameterized complexity primer
- What's next? Future directions in parameterized complexity
- Win-win kernelization for degree sequence completion problems
- Chordal editing is fixed-parameter tractable
- Chordal editing is fixed-parameter tractable
- Generalized graph clustering: recognizing (p,q)-cluster graphs
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Proper Interval Vertex Deletion
- Polynomial kernels for proper interval completion and related problems
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized complexity of Eulerian deletion problems
- Parameterized vertex deletion problems for hereditary graph classes with a block property
- Editing to a planar graph of given degrees
- Reducing rank of the adjacency matrix by graph modification
- Reducing rank of the adjacency matrix by graph modification
- Editing graphs into few cliques: complexity, approximation, and kernelization schemes
- Fast quasi-threshold editing
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees
- Wheel-Free Deletion Is W[2]-Hard
- Characterizing and Computing Minimal Cograph Completions
- Obtaining a Planar Graph by Vertex Deletion
- Chordal Deletion Is Fixed-Parameter Tractable
- Clustering with Partial Information
- Two edge modification problems without polynomial kernels
- Parameterized complexity of vertex deletion into perfect graph classes
- Polynomial kernels for proper interval completion and related problems
- The cluster deletion problem for cographs
- Graph-based data clustering with overlaps
- A survey of the algorithmic aspects of modular decomposition
- A faster algorithm for the cluster editing problem on proper interval graphs
This page was built for publication: Fixed-parameter tractability of graph modification problems for hereditary properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1352005)
