Complexity classification of some edge modification problems
From MaRDI portal
This is the complete version of the paper appeared in Lect. Notes Comput. Sci. 1665, 65-77 (1999; Zbl 0952.68112).
Cites work
- A characterization of perfect graphs
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- An Application of Duality to Edge-Deletion Problems
- Asteroidal Triple-Free Graphs
- Bounded degree interval sandwich problems
- Complexity and algorithms for reasoning about time
- Computing the Minimum Fill-In is NP-Complete
- Edge-Deletion Problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Gadgets, Approximation, and Linear Programming
- Graph Classes: A Survey
- Graph Sandwich Problems
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3904630 (Why is no real title available?)
- scientific article; zbMATH DE number 176780 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 554763 (Why is no real title available?)
- scientific article; zbMATH DE number 1953109 (Why is no real title available?)
- scientific article; zbMATH DE number 1559516 (Why is no real title available?)
- scientific article; zbMATH DE number 1420899 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- On intervalizing k-colored graphs for DNA physical mapping
- On the complexity of DNA physical mapping
- Orienting graphs to optimize reachability
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Some complexity results about threshold graphs
- Some simplified NP-complete graph problems
- The approximation of maximum subgraph problems
- The complexity of some edge deletion problems
- The node-deletion problem for hereditary properties is NP-complete
- The splittance of a graph
- Threshold Numbers and Threshold Completions
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
Cited in
(83)- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- Dynamically maintaining split graphs
- Hardness of edge-modification problems
- Blockers and transversals
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- 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}
- Cluster graph modification problems
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- (Sub)linear kernels for edge modification problems toward structured graph classes
- Complexity of edge monitoring on some graph classes
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- Applying modular decomposition to parameterized cluster editing problems
- A new approximate cluster deletion algorithm for diamond-free graphs
- Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
- Modifying a graph using vertex elimination
- Faster parameterized algorithms for deletion to split graphs
- Covering tree with stars
- Additive approximation for edge-deletion problems
- Editing to a connected graph of given degrees
- Parameterized complexity of Eulerian deletion problems
- A cubic-vertex kernel for flip consensus tree
- Minimal comparability completions of arbitrary graphs
- NP-completeness results for edge modification problems
- Prim-based support-graph preconditioners for min-cost flow problems
- Complexity of modification problems for best match graphs
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- On the computational complexity of the bipartizing matching problem
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- Win-win kernelization for degree sequence completion problems
- Chordal editing is fixed-parameter tractable
- Efficient algorithms for Eulerian extension
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Parameterized complexity of Eulerian deletion problems
- Editing to a planar graph of given degrees
- THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
- Graph editing to a fixed target
- Editing graphs into few cliques: complexity, approximation, and kernelization schemes
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Wheel-Free Deletion Is W[2]-Hard
- Graph modification problem for some classes of graphs
- Characterizing and Computing Minimal Cograph Completions
- On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
- Two edge modification problems without polynomial kernels
- Cograph editing: Merging modules is equivalent to editing P₄s
- Orthology relation and gene tree correction: complexity results
- Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- scientific article; zbMATH DE number 2230201 (Why is no real title available?)
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Contracting chordal graphs and bipartite graphs to paths and trees
- Contracting chordal graphs and bipartite graphs to paths and trees
- Matching interdiction
- Polynomial kernels for 3-leaf power graph modification problems
- Splitting plane graphs to outerplanarity
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterized complexity of even/odd subgraph problems
- Strongly chordal and chordal bipartite graphs are sandwich monotone
- Parameterized complexity of the \(\mathcal{T}_{h+1} \)-free edge deletion problem
- A quasi-quadratic vertex-kernel for cograph edge editing
- On the proper interval completion problem within some chordal subclasses
- Splitting plane graphs to outerplanarity
- Complexity and parameterized algorithms for cograph editing
- The st-planar edge completion problem is fixed-parameter tractable
- Exact and heuristic solution approaches for the cluster deletion problem on general graphs
- Parameterized dynamic data structure for split completion
- Editing to a planar graph of given degrees
- On the complexity of vertex-splitting into an interval graph
- Minimal triangulations of graphs: a survey
- A vertex incremental approach for maintaining chordality
- On the effectiveness of the incremental approach to minimal chordal edge modification
- Additive approximation of generalized Turán questions
- Editing to Eulerian graphs
- Minimal split completions
- On the complexity of some subgraph problems
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
- Characterizing and computing minimal cograph completions
- Chordal deletion is fixed-parameter tractable
- On listing, sampling, and counting the chordal graphs with edge constraints
This page was built for publication: Complexity classification of some edge modification problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5948964)
