The complexity of some edge deletion problems
From MaRDI portal
Publication:3801094
DOI10.1109/31.1748zbMath0654.68084OpenAlexW2034115935WikidataQ29040758 ScholiaQ29040758MaRDI QIDQ3801094
Charles J. Colbourn, Ehab S. El-Mallah
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
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)
Related Items
Orthology Relation and Gene Tree Correction: Complexity Results ⋮ Additive approximation of generalized Turán questions ⋮ Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Additive approximation for edge-deletion problems ⋮ Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Complexity of modification problems for best match graphs ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ Linear optimization over homogeneous matrix cones ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Edge deletion to tree-like graph classes ⋮ 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 the sizes of generalized cactus graphs ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ Testing outerplanarity of bounded degree graphs ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ On the flora of asynchronous locally non-monotonic Boolean automata networks ⋮ Efficient stabilization of cooperative matching games ⋮ Complexity and parameterized algorithms for cograph editing ⋮ On the complexity of some subgraph problems ⋮ Characterizing and computing minimal cograph completions ⋮ Complexity classification of some edge modification problems ⋮ NP-completeness results for edge modification problems ⋮ On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions ⋮ On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems ⋮ A polynomial kernel for trivially perfect editing ⋮ Unnamed Item ⋮ A polynomial kernel for diamond-free editing ⋮ Hardness of edge-modification problems
