Hardness of edge-modification problems

DOI10.1016/J.TCS.2009.07.002zbMATH Open1176.68136OpenAlexW1987195907MaRDI QIDQ1034612FDOQ1034612

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

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?

zbMATH Keywords

edit distancehardness of approximationhereditary graph propertiesedge modification problems

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)