Edge-Deletion Problems
From MaRDI portal
Publication:3921260
DOI10.1137/0210021zbMath0468.05043OpenAlexW2059401572MaRDI QIDQ3921260
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210021
Related Items (86)
Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ Additive approximation of generalized Turán questions ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ On Halin subgraphs and supergraphs ⋮ Parameterizing edge modification problems above lower bounds ⋮ Optimal edge ranking of trees in polynomial time ⋮ An approximate max-flow min-cut relation for undirected multicommodity flow, with applications ⋮ A Dynamic Programming Algorithm To Test A Signed Graph For Balance ⋮ A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\) ⋮ Additive approximation for edge-deletion problems ⋮ Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Restrictions of minimum spanner problems ⋮ Maximal chordal subgraphs ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth ⋮ Matching interdiction ⋮ Parameterized complexity of fair deletion problems ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Parameterized aspects of strong subgraph closure ⋮ On subgraph complementation to \(H\)-free graphs ⋮ On the approximability of the maximum common subgraph problem ⋮ Separator-based data reduction for signed graph balancing ⋮ A Note on the Minimum H-Subgraph Edge Deletion ⋮ Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ On the computational complexity of the bipartizing matching problem ⋮ A modeling and computational study of the frustration index in signed networks ⋮ The node-deletion problem for hereditary properties is NP-complete ⋮ Games on Graphs: Cop and Robber, Hungry Spiders, and Broadcast Domination ⋮ Minimum \(d\)-blockers and \(d\)-transversals in graphs ⋮ Edge deletion to tree-like graph classes ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Unnamed Item ⋮ Proper interval vertex deletion ⋮ Contracting graphs to paths and trees ⋮ Local approximations for maximum partial subgraph problem. ⋮ A simple variant of node connectivity is NP-complete ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ The approximation of maximum subgraph problems ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ The complexity of the reliable connectivity problem ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ A spectral method for bipartizing a network and detecting a large anti-community ⋮ Efficient stabilization of cooperative matching games ⋮ SPLITTING NUMBER is NP-complete ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ On the complexity of some subgraph problems ⋮ Unnamed Item ⋮ Complexity classification of some edge modification problems ⋮ The complexity of total edge domination and some related results on trees ⋮ On maximum planar induced subgraphs ⋮ NP-completeness results for edge modification problems ⋮ Properties of \(\pi\)-skew graphs with applications ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Unnamed Item ⋮ A polynomial kernel for trivially perfect editing ⋮ Feedback edge sets in temporal graphs ⋮ Unnamed Item ⋮ On the parameterized complexity of graph modification to first-order logic properties ⋮ The complexity of generalized clique covering ⋮ Composition of graphs and the triangle-free subgraph polytope ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Bandwidth contrained NP-complete problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs ⋮ Hardness of edge-modification problems ⋮ On the complexity of the approximation of nonplanarity parameters for cubic graphs ⋮ On Generating Triangle-Free Graphs ⋮ On the skewness of Cartesian products with trees ⋮ Blockers and transversals ⋮ A balm: defend the clique-based attack from a fundamental aspect ⋮ Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid ⋮ On subgraph complementation to \(H\)-free Graphs ⋮ Edge-contraction problems ⋮ Parameterized complexity of finding subgraphs with hereditary properties. ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Modifying a graph using vertex elimination ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ \(K_ i\)-covers. I: Complexity and polytopes
This page was built for publication: Edge-Deletion Problems
