NP-completeness results for edge modification problems
From MaRDI portal
Publication:2500532
DOI10.1016/J.DAM.2006.03.031zbMATH Open1110.68094OpenAlexW2104894563MaRDI QIDQ2500532FDOQ2500532
Authors: Pablo Burzyn, Guillermo Durán, Flavia Bonomo 
Publication date: 17 August 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.03.031
Recommendations
- Publication:4944968
- Parameterized lower bounds and dichotomy results for the NP-completeness of \(H\)-free edge modification problems
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- Graph modification problem for some classes of graphs
- Node-and edge-deletion NP-complete problems
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- On the complexity of DNA physical mapping
- Title not available (Why is that?)
- Graph Classes: A Survey
- On intervalizing \(k\)-colored graphs for DNA physical mapping
- On local convexity in graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Linear-time recognition of circular-arc graphs
- Orienting graphs to optimize reachability
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Title not available (Why is that?)
- Some simplified NP-complete graph problems
- Recognizing Berge graphs
- Representation of a finite graph by a set of intervals on the real line
- The splittance of a graph
- Computing the Minimum Fill-In is NP-Complete
- Recognition of Circle Graphs
- Title not available (Why is that?)
- Complexity classification of some edge modification problems
- Algorithms for weakly triangulated graphs
- Clique Graphs of Chordal and Path Graphs
- Edge-Deletion Problems
- Title not available (Why is that?)
- Bicliques in graphs. I: Bounds on their number
- The complexity of some edge deletion problems
- Polynomial time recognition of unit circular-arc graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some complexity results about threshold graphs
- Title not available (Why is that?)
- Coordinated graphs and clique graphs of clique-Helly perfect graphs
- Title not available (Why is that?)
Cited In (46)
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Characterizing and computing minimal cograph completions
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Editing to a connected graph of given degrees
- MPF problem over modified medial semigroup is NP-complete
- Biclique-Helly graphs
- Title not available (Why is that?)
- Reducing rank of the adjacency matrix by graph modification
- An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
- Blockers and transversals
- On the hardness of solving edge matching puzzles as SAT or CSP problems
- On the computational complexity of the bipartizing matching problem
- Two edge modification problems without polynomial kernels
- Parameterized complexity of Eulerian deletion problems
- A cubic-vertex kernel for flip consensus tree
- Unit interval editing is fixed-parameter tractable
- Characterizing and Computing Minimal Cograph Completions
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- A survey of parameterized algorithms and the complexity of edge modification
- Switches in Eulerian graphs
- Parameterized complexity of Eulerian deletion problems
- NP-completeness for minimizing maximum edge length in grid embeddings
- Matching interdiction
- An NP-completeness result of edge search in graphs
- Indirect identification of horizontal gene transfer
- Two edge modification problems without polynomial kernels
- A polynomial kernel for trivially perfect editing
- On the threshold of intractability
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Exact-2-relation graphs
- Graph editing to a fixed target
- Reducing rank of the adjacency matrix by graph modification
- Critical edges for the assignment problem: complexity and exact resolution
- Graph modification problem for some classes of graphs
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- Efficient algorithms for Eulerian extension
- Editing to Eulerian graphs
- Exploring the subexponential complexity of completion problems
- Editing to a graph of given degrees
- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Complexity and parameterized algorithms for cograph editing
- Editing to a planar graph of given degrees
- Editing to a planar graph of given degrees
- (Sub)linear kernels for edge modification problems toward structured graph classes
- An \(O(n^2)\) time algorithm for the minimal permutation completion problem
This page was built for publication: NP-completeness results for edge modification problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500532)
