An Application of Duality to Edge-Deletion Problems

DOI10.1137/0216024zbMath0634.68033OpenAlexW1965628631MaRDI QIDQ3773336

Takao 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

dualityplanar graphsconnectivityouterplanarNP-completeedge-deletion problemseries-parallel

Mathematics Subject Classification ID

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

Related Items (7)

A graph approximation heuristic for the vertex cover problem on planar graphs ⋮ Additive approximation of generalized Turán questions ⋮ On Halin subgraphs and supergraphs ⋮ Additive approximation for edge-deletion problems ⋮ On the complexity of some subgraph problems ⋮ Complexity classification of some edge modification problems ⋮ Hardness of edge-modification problems

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