Hardness of edge-modification problems
type: Item
instance of: scholarly article
title: Hardness of edge-modification problems
zbMATH Open document ID: 1176.68136
author: Noga Alon
author: Uri Stav
published in: Theoretical Computer Science
publication date: 2009-11-06T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5626962
zbMATH Keywords: edge modification problems
zbMATH Keywords: hardness of approximation
zbMATH Keywords: edit distance
zbMATH Keywords: hereditary graph properties
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.07.002
OpenAlex ID: W1987195907
cites work: Ranking Tournaments
cites work: Additive approximation for edge-deletion problems
cites work: What is the furthest graph from a hereditary property?
cites work: The maximum edit distance from hereditary graph properties
cites work: Stability‐type results for hereditary properties
cites work: \(H\)-free graphs of large minimum degree
cites work: On the connection between chromatic number, maximal clique and minimal degree of a graph
cites work: An Application of Duality to Edge-Deletion Problems
cites work: Correlation clustering
cites work: Q3852212
cites work: On the hardness of approximating minimum vertex cover
cites work: The complexity of some edge deletion problems
cites work: Testing versus estimation of graph properties
cites work: Q4193514
cites work: Q4198056
cites work: Q3328583
cites work: On the complexity of DNA physical mapping
cites work: The splittance of a graph
cites work: Complexity classification of some edge modification problems
cites work: Q4770411
cites work: Q5683627
cites work: Cluster graph modification problems
cites work: Edge-Deletion Problems
DOI: 10.1016/J.TCS.2009.07.002
description: scientific article; zbMATH DE number 5626962