Fixed-parameter tractability of graph modification problems for hereditary properties
From MaRDI portal
Publication:1352005
DOI10.1016/0020-0190(96)00050-6zbMATH Open0875.68702DBLPjournals/ipl/Cai96OpenAlexW2144050783WikidataQ56474996 ScholiaQ56474996MaRDI QIDQ1352005FDOQ1352005
Authors: Leizhen Cai 
Publication date: 27 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(96)00050-6
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complement reducible graphs
- Node-Deletion NP-Complete Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Node-and edge-deletion NP-complete problems
- Generating binary trees by transpositions
- Algorithmic Aspects of Vertex Elimination on Graphs
- Title not available (Why is that?)
- Computing the Minimum Fill-In is NP-Complete
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- On the complexity of the maximum subgraph problem
Cited In (only showing first 100 items - show all)
- On the effectiveness of the incremental approach to minimal chordal edge modification
- Characterizing and computing minimal cograph completions
- Conflict free version of covering problems on graphs: classical and parameterized
- On structural parameterizations of load coloring
- Parameterized enumeration for modification problems
- Assessing the computational complexity of multi-layer subgraph detection
- Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Cograph editing: Merging modules is equivalent to editing P_4s
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- Paths to trees and cacti
- Parameterizing edge modification problems above lower bounds
- The birth and early years of parameterized complexity
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- Additive approximation of generalized Turán questions
- Chordal Deletion Is Fixed-Parameter Tractable
- Fast quasi-threshold editing
- Reconstructing gene trees from Fitch's xenology relation
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Fixed-parameter tractable distances to sparse graph classes
- On the parameterized complexity of contraction to generalization of trees
- Paths to trees and cacti
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- A Polynomial Kernel for Diamond-Free Editing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parameterized complexity of vertex deletion into perfect graph classes
- A survey of parameterized algorithms and the complexity of edge modification
- Faster parameterized algorithm for cluster vertex deletion
- On the interval completion of chordal graphs
- Parameterized aspects of strong subgraph closure
- Polynomial kernels for paw-free edge modification problems
- Two edge modification problems without polynomial kernels
- An FPT algorithm for the vertex cover \(P_4\) problem
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
- Obtaining split graphs by edge contraction
- Vertex deletion problems on chordal graphs
- Complexity of modification problems for reciprocal best match graphs
- Minimum fill-in of sparse graphs: kernelization and approximation
- Wheel-Free Deletion Is W[2]-Hard
- On structural parameterizations of firefighting
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- On the Advice Complexity of Online Edge- and Node-Deletion Problems
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- Title not available (Why is that?)
- Polynomial kernelization for removing induced claws and diamonds
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- A polynomial kernel for diamond-free editing
- Structural parameterizations of Tracking Paths problem
- Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
- Polynomial kernelization for removing induced claws and diamonds
- A naive algorithm for feedback vertex set
- Parameterized complexity of the induced subgraph problem in directed graphs
- An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover}
- Online node- and edge-deletion problems with advice
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Faster and enhanced inclusion-minimal cograph completion
- Parameterized complexity of vertex deletion into perfect graph classes
- Polynomial kernels for proper interval completion and related problems
- The cluster deletion problem for cographs
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- A fast branching algorithm for cluster vertex deletion
- Title not available (Why is that?)
- Parameterized complexity of even/odd subgraph problems
- Parameterized complexity of finding connected induced subgraphs
- Editing to a connected graph of given degrees
- On the vertex cover \(P_3\) problem parameterized by treewidth
- An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- What's next? Future directions in parameterized complexity
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- Graph-based data clustering with overlaps
- A basic parameterized complexity primer
- Fixed-parameter algorithms for cluster vertex deletion
- Parameterized Graph Editing with Chosen Vertex Degrees
- Edge deletion problems: branching facilitated by modular decomposition
- Editing graphs into disjoint unions of dense clusters
- Parameterized complexity of finding regular induced subgraphs
- Proper interval vertex deletion
- Two edge modification problems without polynomial kernels
- Structural parameterizations for boxicity
- Fixed-parameter complexity of minimum profile problems
- Parameterized complexity of Eulerian deletion problems
- Dynamic parameterized problems
- Parameterized complexity of finding subgraphs with hereditary properties.
- Win-win kernelization for degree sequence completion problems
- Chordal editing is fixed-parameter tractable
- Minimal triangulations of graphs: a survey
- The Multi-parameterized Cluster Editing Problem
- Unit interval editing is fixed-parameter tractable
- The parameterized complexity of \(k\)-edge induced subgraphs
- Characterizing and Computing Minimal Cograph Completions
- Additive approximation for edge-deletion problems
- Complexity classification of some edge modification problems
- Parameterized coloring problems on chordal graphs
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Obtaining a planar graph by vertex deletion
- Applying modular decomposition to parameterized cluster editing problems
- Chordal deletion is fixed-parameter tractable
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)
