Edge deletion to tree-like graph classes
From MaRDI portal
Publication:6124427
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
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