An Application of Duality to Edge-Deletion Problems

DOI10.1137/0216024MaRDI QIDQ3773336zbMATH OpenOpenAlexFDO

Authors T. Asano

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0216024

zbMATH Keywords

connectivitydualityedge-deletion problemNP-completeouterplanarplanar graphsseries-parallel

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Node-and edge-deletion NP-complete problems
• scientific article; zbMATH DE number 4089594
• The complexity of some edge deletion problems
• EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
• On maximum planar induced subgraphs

Cited in

(14)

• Hardness of edge-modification problems
• A graph approximation heuristic for the vertex cover problem on planar graphs
• On Halin subgraphs and supergraphs
• Edge deletion preserving the diameter of the hypercube
• Additive approximation for edge-deletion problems
• The complexity of some edge deletion problems
• scientific article; zbMATH DE number 4089594 (Why is no real title available?)
• EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
• Dilation-Optimal Edge Deletion in Polygonal Cycles
• Complexity classification of some edge modification problems
• Edge deletion to tree-like graph classes
• Trimming forests is hard (unless they are made of stars)
• Additive approximation of generalized Turán questions
• On the complexity of some subgraph problems

This page was built for publication: An Application of Duality to Edge-Deletion Problems

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