NP-completeness results for edge modification problems
type: Item
instance of: scholarly article
title: NP-completeness results for edge modification problems
zbMATH Open document ID: 1110.68094
author: Pablo Burzyn
author: Guillermo Durán
author: Flavia Bonomo
published in: Discrete Applied Mathematics
publication date: 2006-08-17T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5047514
zbMATH Keywords: computational complexity
zbMATH Keywords: edge modification problems
zbMATH Keywords: graph classes
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
full work available at URL: j.dam.2006.03.031
OpenAlex ID: W2104894563
cites work: On intervalizing \(k\)-colored graphs for DNA physical mapping
cites work: Q3595114
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Graph Classes: A Survey
cites work: Q5708487
cites work: Recognizing Berge graphs
cites work: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
cites work: Q4810370
cites work: Polynomial time recognition of unit circular-arc graphs
cites work: Q5461444
cites work: The complexity of some edge deletion problems
cites work: On local convexity in graphs
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Q3328583
cites work: On the complexity of DNA physical mapping
cites work: Orienting graphs to optimize reachability
cites work: The splittance of a graph
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Some complexity results about threshold graphs
cites work: Linear-time recognition of circular-arc graphs
cites work: Q5501778
cites work: Complexity classification of some edge modification problems
cites work: Q4373687
cites work: Bicliques in graphs. I: Bounds on their number
cites work: Q5683627
cites work: Recognition of Circle Graphs
cites work: Algorithms for weakly triangulated graphs
cites work: Q4940014
cites work: Clique Graphs of Chordal and Path Graphs
cites work: Computing the Minimum Fill-In is NP-Complete
cites work: Edge-Deletion Problems
DOI: 10.1016/J.DAM.2006.03.031
description: scientific article