The complexity of some edge deletion problems

DOI10.1109/31.1748zbMATH Open0654.68084OpenAlexW2034115935WikidataQ29040758 ScholiaQ29040758MaRDI QIDQ3801094FDOQ3801094

Authors: Charles J. Colbourn, Ehab S. Elmallah 

Publication date: 1988

Published in: IEEE Transactions on Circuits and Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/31.1748

Recommendations

• scientific article; zbMATH DE number 4089594
• Node-and edge-deletion NP-complete problems
• An Application of Duality to Edge-Deletion Problems
• EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
• Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems

zbMATH Keywords

complexityNP-hardedge deletionforbidden homeomorphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Cited In (49)

• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Edge deletion preserving the diameter of the hypercube
• Characterizing and computing minimal cograph completions
• Title not available (Why is that?)
• Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
• On the complexity of some subgraph problems
• NP-completeness results for edge modification problems
• Linear optimization over homogeneous matrix cones
• Node-and edge-deletion NP-complete problems
• Hardness of edge-modification problems
• Edge deletion problems: branching facilitated by modular decomposition
• Additive approximation of generalized Turán questions
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Cutting a tree with subgraph complementation is hard, except for some small trees
• How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks
• Cutting a tree with subgraph complementation is hard, except for some small trees
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• A Polynomial Kernel for Line Graph Deletion
• Title not available (Why is that?)
• A Polynomial Kernel for Diamond-Free Editing
• Finding the root graph through minimum edge deletion
• A Note on the Minimum H-Subgraph Edge Deletion
• On the flora of asynchronous locally non-monotonic Boolean automata networks
• Characterizing and Computing Minimal Cograph Completions
• Additive approximation for edge-deletion problems
• Complexity classification of some edge modification problems
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• On the sizes of generalized cactus graphs
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• Complexity of modification problems for best match graphs
• An Application of Duality to Edge-Deletion Problems
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• Trimming forests is hard (unless they are made of stars)
• On the complexity of singly connected vertex deletion
• Testing outerplanarity of bounded degree graphs
• Dichotomy results on the hardness of \(H\)-free edge modification problems
• Title not available (Why is that?)
• A polynomial kernel for diamond-free editing
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• Tree-edges deletion problems with bounded diameter obstruction sets
• Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems
• Complexity and parameterized algorithms for cograph editing
• Parameterized vertex deletion problems for hereditary graph classes with a block property
• Orthology relation and gene tree correction: complexity results
• Edge deletion to tree-like graph classes
• Efficient stabilization of cooperative matching games

This page was built for publication: The complexity of some edge deletion problems

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