Edge deletion to tree-like graph classes

DOI10.1016/j.dam.2024.01.028arXiv2210.03839WikidataQ128814048 ScholiaQ128814048MaRDI QIDQ6124427

Nina Pardal, Ivo Koch, Vinícius Fernandes dos Santos

Publication date: 27 March 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2210.03839

zbMATH Keywords

sparse graph classesedge deletion problemsmodification problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Dominating sets for split and bipartite graphs
• Clustering and domination in perfect graphs
• Hamiltonian circuits in interval graph generalizations
• The node-deletion problem for hereditary properties is NP-complete
• Matroid matching and some applications
• A partial k-arboretum of graphs with bounded treewidth
• Chordal completions of planar graphs
• On the complexity of DNA physical mapping
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• The path partition problem and related problems in bipartite graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The complexity of some edge deletion problems
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Edge-Deletion Problems
• Hamilton Paths in Grid Graphs
• An induced subgraph characterization of domination perfect graphs

This page was built for publication: Edge deletion to tree-like graph classes