Hardness of edge-modification problems

DOI10.1016/J.TCS.2009.07.002MaRDI QIDQ1034612zbMATH OpenOpenAlexFDO

Authors Noga Alon, Uri Stav

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

zbMATH Keywords

edge modification problemsedit distancehardness of approximationhereditary graph properties

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Additive approximation for edge-deletion problems
• Hardness of approximation for \(H\)-free edge modification problems
• Hardness of approximation for \(H\)-free edge modification problems
• Dichotomy results on the hardness of H-free edge modification problems
• What is the furthest graph from a hereditary property?

Cites work

• H-free graphs of large minimum degree
• Additive approximation for edge-deletion problems
• An Application of Duality to Edge-Deletion Problems
• Cluster graph modification problems
• Complexity classification of some edge modification problems
• Correlation clustering
• Edge-Deletion Problems
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• On the complexity of DNA physical mapping
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the hardness of approximating minimum vertex cover
• Ranking Tournaments
• Stability-type results for hereditary properties
• Testing versus estimation of graph properties
• The complexity of some edge deletion problems
• The maximum edit distance from hereditary graph properties
• The splittance of a graph
• What is the furthest graph from a hereditary property?

Cited in

(8)

• Additive approximation for edge-deletion problems
• On the computational complexity of the bipartizing matching problem
• Stability-type results for hereditary properties
• The edit distance function and symmetrization
• On the computation of edit distance functions
• Dichotomy results on the hardness of H-free edge modification problems
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Cutting a tree with subgraph complementation is hard, except for some small trees

This page was built for publication: Hardness of edge-modification problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1034612)