Hardness of edge-modification problems
From MaRDI portal
Publication:1034612
DOI10.1016/j.tcs.2009.07.002zbMath1176.68136OpenAlexW1987195907MaRDI QIDQ1034612
Publication date: 6 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.002
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (6)
Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ The edit distance function and symmetrization ⋮ On the computational complexity of the bipartizing matching problem ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ On the computation of edit distance functions ⋮ Stability‐type results for hereditary properties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Correlation clustering
- On the hardness of approximating minimum vertex cover
- \(H\)-free graphs of large minimum degree
- The maximum edit distance from hereditary graph properties
- The splittance of a graph
- On the complexity of DNA physical mapping
- On the connection between chromatic number, maximal clique and minimal degree of a graph
- Cluster graph modification problems
- Additive approximation for edge-deletion problems
- What is the furthest graph from a hereditary property?
- Testing versus estimation of graph properties
- Stability‐type results for hereditary properties
- An Application of Duality to Edge-Deletion Problems
- The complexity of some edge deletion problems
- Edge-Deletion Problems
- Ranking Tournaments
- Complexity classification of some edge modification problems
This page was built for publication: Hardness of edge-modification problems
