Edge-Deletion Problems - MaRDI portal

Cited in

(91)

Hardness of edge-modification problems
Blockers and transversals
Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
Combinatorial analysis (nonnegative matrices, algorithmic problems)
$K_ i$-covers. I: Complexity and polytopes
Maximal chordal subgraphs
The node-deletion problem for hereditary properties is NP-complete
The complexity of the reliable connectivity problem
The complexity of generalized clique covering
On Halin subgraphs and supergraphs
Restrictions of minimum spanner problems
Local approximations for maximum partial subgraph problem.
Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
On polynomial kernelization of $\mathcal H$-\textsc{free edge deletion}
Composition of graphs and the triangle-free subgraph polytope
Bandwidth contrained NP-complete problems
On the complexity of the approximation of nonplanarity parameters for cubic graphs
Parameterized complexity of finding subgraphs with hereditary properties.
Optimal edge ranking of trees in polynomial time
An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
A min-max relation for $K_ 3$-covers in graphs noncontractible to $K_ 5\backslash e$
Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
Proper interval vertex deletion
Algorithmic aspects of clique-transversal and clique-independent sets
A spectral method for bipartizing a network and detecting a large anti-community
The complexity of total edge domination and some related results on trees
Properties of $\pi$-skew graphs with applications
Incompressibility of $H$-free edge modification problems: towards a dichotomy
A balm: defend the clique-based attack from a fundamental aspect
On subgraph complementation to $H$-free Graphs
Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
Parameterized aspects of strong subgraph closure
Edge deletion problems: branching facilitated by modular decomposition
On the parameterized complexity of graph modification to first-order logic properties
On the skewness of Cartesian products with trees
Modifying a graph using vertex elimination
Additive approximation for edge-deletion problems
Polynomial kernelization for removing induced claws and diamonds
On maximum planar induced subgraphs
NP-completeness results for edge modification problems
On subgraph complementation to $H$-free graphs
On the computational complexity of the bipartizing matching problem
Exploring the subexponential complexity of completion problems
On generating triangle-free graphs
Networks with unicyclic connected components and without short cycles
A Note on the Minimum H-Subgraph Edge Deletion
Planarization and acyclic colorings of subcubic claw-free graphs
Parameterized lower bound and NP-completeness of some $H$-free edge deletion problems
A simple variant of node connectivity is NP-complete
Minimum $d$-blockers and $d$-transversals in graphs
The approximation of maximum subgraph problems
Parameterized complexity of three edge contraction problems with degree constraints
A Dynamic Programming Algorithm To Test A Signed Graph For Balance
A Polynomial Kernel for Diamond-Free Editing
Destroying Bicolored $P_3$s by Deleting Few Edges
Parameterized complexity of fair vertex evaluation problems
On the approximability of the maximum common subgraph problem
Parameterized aspects of strong subgraph closure
Efficient stabilization of cooperative matching games
Minimum-weight subgraphs with unicyclic components and a lower-bounded girth
Dichotomy results on the hardness of H-free edge modification problems
Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
scientific article; zbMATH DE number 2230201 (Why is no real title available?)
scientific article; zbMATH DE number 2230213 (Why is no real title available?)
Graph theory (algorithmic, algebraic, and metric problems)
A Polynomial Kernel for Line Graph Deletion
Chordless Cycle Packing Is Fixed-Parameter Tractable
Incompressibility of H-free edge modification problems: towards a dichotomy
Feedback edge sets in temporal graphs
SPLITTING NUMBER is NP-complete
Complexity classification of some edge modification problems
Matching interdiction
A modeling and computational study of the frustration index in signed networks
Games on Graphs: Cop and Robber, Hungry Spiders, and Broadcast Domination
Edge deletion to tree-like graph classes
Separator-based data reduction for signed graph balancing
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
Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity
Quantum graph drawing (best student paper)
Cutting a tree with subgraph complementation is hard, except for some small trees
Trimming forests is hard (unless they are made of stars)
Listing maximal H-free subgraphs
Vertex identification to a forest
Compound logics for modification problems
Parameterised distance to local irregularity
Kernelization in almost linear time for clustering into bounded vertex cover components
Edge-contraction problems
Additive approximation of generalized Turán questions
On the complexity of some subgraph problems

This page was built for publication: Edge-Deletion Problems

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